Codeforces ECR #006 : F. Xors on Segments

あれ？
http://codeforces.com/contest/620/problem/F

問題

f(u,v)はu xor u+1 xor ... xor vとする。(u≦v)
以下のクエリM個の答えよ。

各クエリは2値(L,R)で構成される。
A[L...R]から2値x,yを選ぶ場合f(x,y)の取り得る最大値を答えよ。

解法

想定解はMo's Algorithmなのだが…。
愚直にO(N^2)通りf(A[L],A[R])を列挙しても間に合ってしまうようだ。

int N,M;
int A[50050],X[50500];
int L[50050],R[50500];

int XX[1010101];
int ma[50505];
int ret[50505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=1000000;i++) XX[i]=XX[i-1]^i;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i], X[i]=XX[A[i]];
	FOR(i,M) cin>>L[i]>>R[i], L[i]--,R[i]--;
	
	FOR(x,N) {
		ma[x-1]=0;
		for(y=x;y<N;y++) ma[y]=max(ma[y-1],X[x]^X[y]^((A[x]>A[y])?A[y]:A[x]));
		FOR(i,M) if(L[i]<=x) ret[i]=max(ret[i],ma[R[i]]);
	}
	
	FOR(i,M) cout<<ret[i]<<endl;
}

まとめ

あのテク、Mo's algorithmっていうのね。