Description
给一个1到N的排列{Ai}，询问是否存在1<=p1<p2<p3<p4<p5<…<pLen<=N (Len>=3)，
使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。
Input
输入的第一行包含一个整数T，表示组数。
下接T组数据，每组第一行一个整数N，每组第二行为一个1到N的排列，数字两两之间用空格隔开。
N<=10000，T<=7
Output
对于每组数据，如果存在一个等差子序列，则输出一行“Y”，否则输出一行“N”。
Sample Input
2
3
1 3 2
3
3 2 1
3
1 3 2
3
3 2 1
Sample Output
N
Y
Solution
发现只用求是否存在长度为$3$的等差子序列就够了。
对于一个$a_i$，若$a_i-k$和$a_i+k$都在他前面出现才不会有$(a_i-k,a_i,a_i+k)$这个等差子序列出现。
所以可以从前往后枚举，出现为$1$未出现为$0$。可以用线段树维护区间$hash$判断以$a_i$为中心是否回文。
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#define N (10009)
#define LL unsigned long long
using namespace std; int T,n,flag,a[N];
LL Segt[N<<][],base[N]; inline int read()
{
int x=,w=; char c=getchar();
while (c<'' || c>'') {if (c=='-') w=-; c=getchar();}
while (c>='' && c<='') x=x*+c-'', c=getchar();
return x*w;
} void Update(int now,int l,int r,int x)
{
if (l==r) {Segt[now][]=Segt[now][]=; return;}
int mid=(l+r)>>;
if (x<=mid) Update(now<<,l,mid,x);
else Update(now<<|,mid+,r,x);
Segt[now][]=Segt[now<<][]*base[r-mid]+Segt[now<<|][];
Segt[now][]=Segt[now<<|][]*base[mid-l+]+Segt[now<<][];
} LL Query(int now,int l,int r,int l1,int r1,int d)
{
if (l1<=l && r<=r1) return Segt[now][d];
int mid=(l+r)>>;
if (r1<=mid) return Query(now<<,l,mid,l1,r1,d);
else if (l1>mid) return Query(now<<|,mid+,r,l1,r1,d);
else if(d==) return Query(now<<,l,mid,l1,mid,d)*base[r1-mid]+Query(now<<|,mid+,r,mid+,r1,d);
else if(d==) return Query(now<<|,mid+,r,mid+,r1,d)*base[mid-l1+]+Query(now<<,l,mid,l1,mid,d);
} void Solve(int x)
{
Update(,,n,x);
if (x== || x==n) return;
int L=min(x-,n-x);
LL lh=Query(,,n,x-L,x-,);
LL rh=Query(,,n,x+,x+L,);
if (lh!=rh) flag=;
} int main()
{
T=read();
base[]=;
for (int i=; i<=; ++i) base[i]=base[i-]*;
while (T--)
{
memset(Segt,,sizeof(Segt));
n=read(); flag=;
for (int i=; i<=n; ++i)
{
int x=read();
if (!flag) Solve(x);
}
puts(flag?"Y":"N");
}
}