http://www.zybbs.org/JudgeOnline/problem.php?id=2124

这道题挺好的，但是我怎么找不到题解呢……是神犇们觉得这题过于简单还是我查的关键词不对？

题意是，给定10000个数的排列，问是否存在长度为3的子序列[tex]$A_{x1}$,$A_{x2}$,$A_{x3}$[/tex]，使得[tex]$A_{x2}-A_{x1}=A_{x3}-A_{x2}$[/tex]。

从数据范围估计，大概每个询问需要O(nlogn)左右的复杂度。观察到给出的数字是1~N的排列，这不止说明数字范围在1~N之内，还说明每个数出现且仅出现一次。

这个方法确实是非常的巧妙，要从诸多的嫌疑入手点中抓住这一点对于我这个弱菜来说真的非常难，在此膜拜杨天大神。

用类似离线的算法，从左到右依次加入数字，并且查询这个数字x是否可以作为等差中项。假设公差的绝对值是k，则三个数字分别是：x-k,x,x+k。如果此时，x-k与x+k两数一个已经出现过了，另一个没有出现过，则TAK了。

一个个枚举k肯定是不行的，所以做到这里很容易就会觉得这个方法不对……然后就没有然后了……

分析一下，比较的那些数字的状态分别是：

只要这些状态上下有一组不同（即一个出现过，一个没有出现过）则TAK。可以发现当将这串01状态看成二进制数字时，NIE的充要条件是两数相等。

如果N比较小，则算法呼之欲出：用线段树维护一段内的状态（正过去一个二进制数字，反过来一个二进制数字），然后每次比较x-1...x-k和x+1...x+k（k表示min(n-x,x),即向头尾延伸最长伸到哪里）这两条线段上的状态是否完全一样即可。

这样出现了两个问题，一个是怎么合并两条线段（这个很好想，下面也要用到），另一个是N很大，数字要变成高精度了，怎么办？

答案是……BKDRHASH……做过火星人prefix/增强型LCP的同学应该可以直接开始写代码了……

看成二进制数字不太好做，那么就看成字符串，然后HASH起来，只要HASH值一样，字符串就一样……

而BKDRHASH的好处就是可以随便乱搞，乱改，乱弄……这里不理解的同学去做做火星人prefix就可以了……

#include <stdio.h>
#include <string.h>
int a[32768][2],n,M;
char str[1000000],*p=str;
inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}inline void Update(i){
	int P=101;i+=M-1;
	for(a[i][0]=a[i][1]=1;i>>=1;P=P*P)a[i][0]=a[i<<1][0]*P+a[i<<1^1][0],a[i][1]=a[i<<1^1][1]*P+a[i<<1][1];
}inline Query(i,j,c)int i,j;_Bool c;{
	int ans[2]={0,0},P=101,lP=1,rP=1;
#define link(a,b,c,lP,rP) c?b*lP+a:a*rP+b
	for(i+=M-2,j+=M;i^j^1;i>>=1,j>>=1,P*=P){
		if(~i&1)ans[0]=link(ans[0],a[i^1][c],c,lP,P),lP*=P;
		if(j&1)ans[1]=link(a[j^1][c],ans[1],c,P,rP),rP*=P;
	}return link(ans[0],ans[1],c,lP,rP);
}main(){
	int t,i,s,k;fread(p,1,1000000,stdin);
	for(t=getint();t--;puts(i==-1?"N":"Y"))for(memset(a,0,(M=1<<32-__builtin_clz((i=n=getint())-1))<<4);i--;Update(s))if((s=getint())!=1&&s!=n){
		k=s-1>n-s?n-s:s-1;
		if(Query(s-k,s-1,1)!=Query(s+1,s+k,0)){while(*p++!='\n');break;}
	}return 0;
}

• inline
• block