[文章目录]
Description
给一个1到N的排列{Ai}，询问是否存在1<=p1< p2< p3< p4< p5<…< pLen<=N (Len>=3)，使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。N<=10000，T<=7
分段hash+桶。
考虑我们将每个数扔进桶里，枚举到一个x。如果x不构成任意一个等差数列当且仅当对于每两个值x-d,x+d在桶中都出现或者没出现，也就是说桶里关于x对称。那么我们维护桶的hash值，每次判断关于当前值ai是否回文，如果回文则修改，继续判断下一个，反之则说明存在等差数列的三项。时间复杂度O(nlogn)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
const int bas=233;
int n,a[10010];
ull bin[10010];
struct hass
{
ull h1,h2;
};
struct seg
{
ull h1[40010],h2[40010];
void clear(){memset(h1,0,sizeof h1); memset(h2,0,sizeof h2);}
void pushup(int pos,int l1,int l2)
{
h1[pos]=h1[pos<<1]+h1[pos<<1|1]*bin[l1];
h2[pos]=h2[pos<<1|1]+h2[pos<<1]*bin[l2];
}
void fix(int pos,int l,int r,int x)
{
if(l==r) {h1[pos]=h2[pos]=1;return;}
int mid=(l+r)>>1;
if(x<=mid) fix(pos<<1,l,mid,x);
else fix(pos<<1|1,mid+1,r,x);
pushup(pos,mid-l+1,r-mid);
}
hass query(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return (hass){h1[pos],h2[pos]};
int mid=(l+r)>>1;
if(y<=mid) return query(pos<<1,l,mid,x,y);
else if(x>mid) return query(pos<<1|1,mid+1,r,x,y);
else
{
hass ls=query(pos<<1,l,mid,x,y);
hass rs=query(pos<<1|1,mid+1,r,x,y);
return (hass){ls.h1+rs.h1*bin[mid-max(x,l)+1],rs.h2+ls.h2*bin[min(r,y)-mid]};
//一定要取max和min，因为当前区间不一定就是大于[x,y]
}
}
}s;
int main()
{
int T; scanf("%d",&T);
bin[0]=1; for(int i=1;i<=10000;++i) bin[i]=bin[i-1]*bas;
while(T--)
{
scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",a+i);
s.clear(); bool fl=0; int len; hass ch;
for(int i=1;i<=n;++i)
{
len=min(a[i]-1,n-a[i]);
ch=s.query(1,1,n,a[i]-len,a[i]+len);
if(ch.h1!=ch.h2) {fl=1; break; }
s.fix(1,1,n,a[i]);
}
if(fl) puts("Y");
else puts("N");
}
return 0;
}