记录编号	601988	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3947.[国家集训队 2011]等差子序列	最终得分	100
用户昵称	左清源	是否通过	通过
代码语言	C++	运行时间	0.631 s
提交时间	2025-06-29 22:08:58	内存使用	8.11 MiB

#include <iostream>
#include <cstdio>
using namespace std;
typedef unsigned long long ull;
const int N=5e5+10;
const int P=131;
struct node{
	ull h1[N<<2],h2[N<<2],pw[N<<2];
	int len[N<<2];
	#define ls (p<<1)
	#define rs (p<<1|1) 
	void push_up(int p){
		h1[p]=h1[ls]+pw[len[ls]]*h1[rs];
		h2[p]=h2[rs]+pw[len[rs]]*h2[ls];
	}
	void build(int p,int l,int r){
		h1[p]=h2[p]=0,len[p]=r-l+1;
		if(l==r)return;int mid=(l+r)>>1;
		build(ls,l,mid),build(rs,mid+1,r);
		return;
	}
	void upd(int p,int l,int r,int x){
		if(l==r){
			h1[p]=h2[p]=1;
		}else{
			int mid=(l+r)>>1;
			if(x<=mid)upd(ls,l,mid,x);
			if(x>mid)upd(rs,mid+1,r,x);
			push_up(p);
		}
		return;
	}
	ull ask1(int p,int l,int r,int L,int R){
		if(L<=l&&r<=R)return h1[p];int mid=(l+r)>>1;
		if(R<=mid)return ask1(ls,l,mid,L,R);
		if(L>mid)return ask1(rs,mid+1,r,L,R);
		return ask1(ls,l,mid,L,R)+pw[mid-max(l,L)+1]*ask1(rs,mid+1,r,L,R);
	}
	ull ask2(int p,int l,int r,int L,int R){
		if(L<=l&&r<=R)return h2[p];int mid=(l+r)>>1;
		if(R<=mid)return ask2(ls,l,mid,L,R);
		if(L>mid)return ask2(rs,mid+1,r,L,R);
		return ask2(rs,mid+1,r,L,R)+pw[min(R,r)-mid]*ask2(ls,l,mid,L,R);
	}
}tr; 
int T,n,a[N],flag;
int main(){
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout); 
	tr.pw[0]=1;
	for(int i=1;i<=500000;i++)tr.pw[i]=tr.pw[i-1]*P;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",a+i);
		tr.build(1,1,n);tr.upd(1,1,n,a[1]);
		flag=0;
		for(int i=2;i<n;i++){
			int len=min(a[i]-1,n-a[i]);
			if(tr.ask1(1,1,n,a[i]-len,a[i])!=tr.ask2(1,1,n,a[i],a[i]+len)){
				flag=1;
				break;
			}
			tr.upd(1,1,n,a[i]); 
		}  
		if(flag)printf("Y\n");
		else printf("N\n");
	}
	return 0;
}