题意
给你一个1~n排列，问有没有一个等差数列（长度至少为3）
题解
我居然自己想到了正解。
但我最后写挂了，所以我又看了题解。
我们维护了一个以权值为下标的01序列。
我们扫描整个序列。对于每一个正在扫描的数，我们判断以这个数的权值作为对称点，01序列是否对称。
这个序列用权值树状数组维护就行。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
const LL mod=1e9+;
int n,t;
const int N=;
LL pw[N],c1[N],c2[N];
int a[N];
int min(int a,int b){
if(a<b)return a;
else return b;
}
int lowbit(int x){
return x&(-x);
}
LL check1(int x){
LL ans=;
for(int i=x;i>=;i-=lowbit(i)){
ans=(ans+(c1[i]*pw[x-i])%mod)%mod;
}
return ans;
}
LL check2(int x){
LL ans=;
for(int i=x;i>=;i-=lowbit(i)){
ans=(ans+(c2[i]*pw[x-i])%mod)%mod;
}
return ans;
}
LL add1(int x){
for(int i=x;i<=n;i+=lowbit(i)){
c1[i]=(c1[i]+pw[i-x])%mod;
}
}
LL add2(int x){
for(int i=x;i<=n;i+=lowbit(i)){
c2[i]=(c2[i]+pw[i-x])%mod;
}
return ;
}
LL query1(int l,int r){
LL p=check1(l-),q=check1(r);
return ((q-p*pw[r-l+])%mod+mod)%mod;
}
LL query2(int l,int r){
LL p=check2(l-),q=check2(r);
return ((q-p*pw[r-l+])%mod+mod)%mod;
}
int main(){
scanf("%d",&t);
pw[]=;
for(int i=;i<=;i++)pw[i]=(pw[i-]*(LL))%mod;
for(int z=;z<=t;z++){
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
memset(c1,,sizeof(c1));memset(c2,,sizeof(c2));
for(int i=;i<=n;i++){
int x=a[i];
int len=min(n-x,x-);
if(len&&query1(x-len,x-)!=query2(n-x-len+,n-x)){printf("Y\n");break;}
add1(x);add2(n-x+);
if(i==n)printf("N\n");
}
}
return ;
}