记录编号	584879	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2011]等差子序列	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.792 s
提交时间	2023-11-16 17:36:21	内存使用	7.54 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//线段树维护字符hash值 
const int N = 1e4+10,mod = 1e9+7;
int q,n;
ll a[N],s[N] = {1};//s数组便于h字符hash合并 2^i
struct T{
    int l,r,len;
    ll s[2];
    #define l(x) t[x].l
    #define r(x) t[x].r 
    #define len(x) t[x].len
    #define s1(x) t[x].s[0]//正序 
    #define s2(x) t[x].s[1]//反序 
}t[N<<4];
void build(int x,int l,int r){
    l(x) = l,r(x) = r,len(x) = r-l+1;
    s1(x) = s2(x) = 0;
    if(l == r)return;
    int mid = l + r >> 1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
}
void pushup(int x){
    s1(x) = ((s1(x<<1) * s[len(x<<1|1)]) % mod + s1(x<<1|1)) % mod;// 
    s2(x) = ((s2(x<<1|1) * s[len(x<<1)]) % mod + s2(x<<1)) % mod;//正序倒序合并 
}
void add(int x,int ed){
    if(l(x) == r(x)){
        s1(x) = s2(x) = 1;
        return;
    }
    int mid = l(x) + r(x) >> 1;
    if(ed <= mid)add(x<<1,ed);
    else add(x<<1|1,ed);
    pushup(x);
}
ll ask(int x,int l,int r,int op){
    if(l <= l(x) && r(x) <= r)return t[x].s[op];
    int mid = l(x) + r(x) >> 1;
    ll ans = 0;int lenl = max(mid-max(l,l(x))+1,0),lenr = max(min(r,r(x))-mid,0);
    if(!op){//正序 
        if(l <= mid)ans += (ask(x<<1,l,r,op) * s[lenr]) % mod;
        if(r > mid)ans += ask(x<<1|1,l,r,op) % mod;// 
    }
    else{//倒序 
        if(l <= mid)ans += ask(x<<1,l,r,op) % mod;
        if(r > mid)ans += (ask(x<<1|1,l,r,op) * s[lenl]) % mod;//
    }
    return ans % mod;
}
int main(){
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    scanf("%d",&q);
    for(int i = 1;i <= 1e4;i++)
        s[i] = s[i-1] * 2 % mod;
    while(q--){
        scanf("%d",&n);build(1,1,n);
        for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
        bool f = 0;
        for(int i = 2;i < n;i++){
            add(1,a[i-1]);
            if(a[i] == 1 || a[i] == n)continue;
            int l = min(a[i]-1,n-a[i]);
            if(ask(1,a[i]-l,a[i]-1,0) != ask(1,a[i]+1,a[i]+l,1)){//不相等就不是回文串 
                printf("Y\n");
                f = 1;
                break;
            }
        }
        if(!f)printf("N\n");
    }
    
    return 0;
    
}