BZOJ 2124: 等差子序列

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 //by NeighThorn
 6 #define int long long
 7 using namespace std;
 8 
 9 const int maxn=10000+5,Mod=1e9+7;
10 
11 int n,cas,flag,p[maxn];
12 
13 struct Tree{
14     
15     long long tr[maxn];
16     
17     inline void clear(void){
18         memset(tr,0,sizeof(tr));
19     }
20     
21     inline void insert(int x,int y){
22         int lala=x;
23         for(;x<=n;x+=x&-x)
24             (tr[x]+=y*p[x-lala])%=Mod;
25     }
26     
27     inline int query(int x){
28         int lala=x,res=0;
29         for(;x;x-=x&-x)
30             (res+=((long long)tr[x]*p[lala-x])%Mod)%Mod;
31         return res;
32     }
33     
34     inline int qry(int l,int r){
35         return ((long long)query(r)-(long long)query(l-1)*p[r-l+1]%Mod+Mod)%Mod;
36     }
37     
38 }a,b;
39 
40 signed main(void){
41     scanf("%lld",&cas);p[0]=1;
42     for(int i=1;i<=10000;i++)
43         p[i]=(p[i-1]<<1)%Mod;
44     while(cas--){
45         scanf("%lld",&n);flag=0;
46         a.clear();b.clear();
47         for(int i=1,x;i<=n;i++){
48             scanf("%lld",&x);
49             if(flag)
50                 continue;
51             int lala=min(x-1,n-x);
52             if(lala&&a.qry(x-lala,x-1)!=b.qry(n-(x+lala)+1,n-(x+1)+1))
53                 puts("Y"),flag=1;
54             a.insert(x,1),b.insert(n-x+1,1);
55         }
56         if(!flag)
57             puts("N");
58     }
59     return 0;    
60 }