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

退役之前出道水题攒RP。好像卡了一些O(msqrtnlogn)的复杂度。。。我不是故意的。。。

我看神犇们的2K+代码，10S+时间，感觉是不是写傻了。。。或者是写了DYF神犇的神算法。。。

这种题首先感觉只有lg好像是不可做的，果断考虑分块。

分成长度为L的块，每块的第一个点叫做关键点，则总共有K=N/L个关键点。

处理出一个K*N的数组，表示每个关键点到之后每个点的答案。这个对于一个关键点是可以O(NlgN)弄出来的，用一般的trie就可以了，这个不会的话可以先去水水USACO再来。

然后对于一个询问(u,v)，可以分解成(u,v)和(X,v)，其中X是u之后的第一个关键点。

那么(X,v)已经处理出来了，剩下的就是u...X这O(L)个数在(u,v)中的max xor了。

问题转化为，求一段内与X的异或最大值。

这个东西用ChairTrie是可以随便减出来的。ChairTrie和ChairTree差不多，就是函数式Trie，从高到低处理X的某一位，如果可以往相反方向走，就走，就可以了。。。懒得说详细了，自己脑补吧。。。

复杂度是O(KNlgN+M(N/K)lgN)，K=sqrtM，总复杂度为O(NsqrtMlgN)，又快又好写  ><

PS：这题在SPOJ上叫做MAXOR我会告诉你们？

#include<cstdio>
#include<algorithm>
#include<cctype>
#define N 12002
#define M 80
using namespace std;
int n,m,ans[M+10][N],S,a[N],re;
struct CT{CT*c[2];int v;}null,*sT[N+1],**T=sT+1,st[N<<5],*stp;
inline int getint(){
	int re=0;char ch;
	while(!isdigit(ch=getchar()));re=ch-48;
	while(isdigit(ch=getchar()))re=re*10+ch-48;
	return re;
}inline int Q(CT*l,CT*r,int x){
	int a=0,k=31;
	while(k--){
		bool c=~x>>k&1;
		if(r->c[c]->v!=l->c[c]->v)a|=1<<k;else c=!c;
		r=r->c[c];l=l->c[c];
	}return a;
}inline CT*I(CT*R,int x){
	CT*r=stp;int k=31;
	while(k--){
		bool c=x>>k&1;
		stp->c[c]=stp+1;
		stp->c[!c]=R->c[!c];
		stp++->v=R->v+1;
		R=R->c[c];
	}stp->c[0]=stp->c[1]=&null;stp++->v=R->v+1;
	return r;
}inline void Init(int ans[N],int i){
	int o=0;stp=st;
	for(T[--i]=&null;++i!=n;T[i]=I(T[i-1],a[i]))o=ans[i]=max(o,Q(&null,T[i-1],a[i]));
}int main(){
	n=getint()+1;m=getint();S=n/M;null.c[0]=null.c[1]=&null;
	for(int i=0;++i!=n;)a[i]=a[i-1]^getint();
	for(int i=M;i--;)Init(ans[i],i*S);
	while(m--){
		re%=n-1;
		int l=(getint()+re)%(n-1),r=(getint()+re)%(n-1);
		if(l>r)l^=r^=l^=r;
		l--;r++;int bl=(l+S)/S;
		re=ans[bl][r];
		while(++l!=r&&l!=bl*S)re=max(re,Q(T[l],T[r],a[l]));
		printf("%d\n",re);
	}return 0;
}

• inline
• block