【题目描述 Description】
给一个 1 到 N 的排列{Ai}，询问是否存在 1<=p1<p2<p3<p4<p5<…<pLen<=N（Len>=3），使得 Ap1,Ap2,Ap3,…ApLen 是一个等差序列。
【输入描述 Input Description】
输入的第一行包含一个整数 T，表示组数。
下接 T 组数据，每组第一行一个整数 N，每组第二行为一个 1 到 N 的排列， 数字两两之间用空格隔开。
【输出描述 Output Description】
对于每组数据，如果存在一个等差子序列，则输出一行“Y”，否则输出一 行“N”。
【样例输入 Sample Input】
2
3
1 3 2
3
3 2 1
【样例输出 Sample Output】
N
Y
【数据范围及提示 Data Size & Hint】
对于5%的数据，N<=100，对于30%的数据，N<=1000，对于100%的数据，N<=10000，T<=7
【解题思路】
首先声明，此题开始并没有什么思路，只找到一个O（N^2）的算法，然而这并没有什么卵用。
老师明示暗示我要我用线段树去做，我苦思冥想没有想出来，于是就抄了题解。
题解是这样的，枚举等差中项，用一颗线段树去维护那些值选了，那些值没选，构成一个01串之后求一个哈希值。
如果出现中项左边的hash值和右边的hash值不一样的情况，就说明存在等差数列，因为证明有一个值在中项左边已经选过，并且与其对应的值在中项右边还没有选。
插入O（logn），查询O（logn），扫一遍O（n）整体O(ologn)；
代码略丑
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=+, mod=;
int xp[maxn],a[maxn],n,v,t;
long long sumv[*maxn][];
//sumv[i][0] 代表从左边扫的值，sumv[i][1]代表从右边扫的值
void updata(int u,int l,int r){
int lc=u<<,rc=lc+;
if (l==r) sumv[u][]=sumv[u][]=;
else{
int mid=(l+r)/;
if (v<=mid) updata(lc,l,mid);
else updata(rc,mid+,r);
sumv[u][]=(sumv[rc][]+xp[r-mid]*sumv[lc][]%mod)%mod;
sumv[u][]=(sumv[lc][]+xp[mid-l+]*sumv[rc][]%mod)%mod;
}
} long long query(int node,int l,int r,int a,int b,int x){
int lc=node<<,rc=lc+;
if (l==a&&r==b) return sumv[node][x];
int mid=(l+r)/;
long long left=,right=;
if (mid<b) right=query(rc,mid+,r,max(mid+,a),b,x);
if (a<=mid) left=query(lc,l,mid,a,min(mid,b),x);
return (x?left+right*xp[max(,mid-a+)]%mod:right+left*xp[max(,b-mid)]%mod)%mod;
} int main(){
scanf("%d",&t);
for (int ii=;ii<t;ii++){
memset(sumv,,sizeof(sumv));
bool flag=;
scanf("%d",&n);
xp[]=;
for (int i=;i<=n+;i++) xp[i]=(xp[i-]<<)%mod;
for (int i=;i<n;i++)scanf("%d",&a[i]);
for (int i=;i<n;i++){
int x=a[i];
int len=min(x-,n-x);//长度取短之后比较
if (len) {
int t1=query(,,n,x+,x+len,);
int t2=query(,,n,x-len,x-,);
if (t1!=t2){
flag=;
break;
}
}
v=x;
updata(,,n);
}
if (flag) printf("Y\n");
else printf("N\n");
}
}
以上为堆状线段树，由于我一直喜欢用结构体，所以就又打了一个，然后发现内存时间代码复杂度都比堆要差，大概是因为要建树和结构体太大的缘故。线段树的种类的确要视题目而定。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=+,mod=;
struct tree{
int l,r,lch,rch;
long long sum;
}tr[maxn*][];
//tr[now][0]代表从左往右, tr[now][1]代表从右往左
int cnt,n,t,xp[maxn],a[maxn]; void build(int now,int l,int r){
cnt++;
tr[cnt][].l=tr[cnt][].l=l; tr[cnt][].r=tr[cnt][].r=r;
if (l==r) return;
tr[cnt][].lch=tr[cnt][].lch=cnt+;
int mid=(l+r)>>;
build(cnt+,l,mid);
tr[now][].rch=tr[now][].rch=cnt+;
build(cnt+,mid+,r);
} long long query(int now,int l,int r,int x){
long long t1=,t2=;
if (tr[now][x].l==l&&tr[now][x].r==r) return tr[now][x].sum;
int mid=(tr[now][x].l+tr[now][x].r)>>;
if (l<=mid) t1=query(tr[now][x].lch,l,min(r,mid),x)%mod;
if (r>mid) t2=query(tr[now][x].rch,max(mid+,l),r,x)%mod;
if (x==) return ((t1*xp[max(,r-mid)])%mod+t2)%mod;
if (x==) return ((t2*xp[max(mid-l+,)])%mod+t1)%mod;
//返回值的时候*xp的时候错过，乘的是数目，虽然我不知道我刚开始为什么写的不对
} void insert(int now,int x){
if (tr[now][].l==x&&tr[now][].r==x){
tr[now][].sum=tr[now][].sum=;
return;
}
int mid=(tr[now][].l+tr[now][].r)>>;
if (x<=mid) insert(tr[now][].lch,x);
if (x>=mid+) insert(tr[now][].rch,x);
int l=tr[now][].l,r=tr[now][].r;
tr[now][].sum=((tr[tr[now][].lch][].sum*xp[r-mid])%mod
+tr[tr[now][].rch][].sum)%mod;
tr[now][].sum=((tr[tr[now][].rch][].sum*xp[mid-l+])%mod
+tr[tr[now][].lch][].sum)%mod;
} int main(){
scanf("%d",&t);
while (t--){
memset(tr,,sizeof(tr));
cnt=;//开始忘记清零CE了
scanf("%d",&n);
xp[]=;
bool flag=;
for (int i=;i<=n+;i++) xp[i]=(xp[i-]<<)%mod;//预处理出所有二的幂
build(,,n);
for (int i=;i<n;i++) scanf("%d",&a[i]);
for (int i=;i<n;i++){
int x=a[i];
int len=min(a[i]-,n-a[i]);
if (len&&query(,x-len,x-,)!=query(,x+,x+len,)){
flag=;
break;
}
insert(,x);
}
if (flag) printf("Y\n");
else printf("N\n");
}
}