Codeforces #340 Div2. E. XOR and Favorite Number

このテク名前あったんだ。
http://codeforces.com/contest/617/problem/E

問題

N要素の数列A[i]が与えられる。

この数列に対し、M個のクエリに答えよ。
各クエリは(L,R)の２値で与えられる。
L≦i≦j≦Rとなる(i,j)のうちA[i] xor A[i+1] xor ... xor A[j] = Kとなる者の数を求めよ。

解法

S[i]=A[0]^A[1]^...^A[i]を事前に計算しておく。
するとA[i] xor A[i+1] xor ... xor A[j] = S[j]^S[i]^A[i]となる。
また、A[i]に対し条件を満たすjはS[j]^S[i]^A[i]=KよりA[i]^S[i] = K^S[j]となるので、K^S[j]の値の登場回数を覚えておけばiに対するjを数え上げられる。
同様にS[i]^A[i]の登場回数も数えておこう。

区間[L,R]に対するクエリの回答が分かっているとき、区間を1変更することは容易である。

• [L-1,R]の解は、[L,R]の解に対しS[L-1]^A[L-1]=K^S[j]となるjの数(K^S[j]の登場回数)を加算すればよい。
• [L,R+1]の解は、[L,R]の解に対しS[i]^A[i]=K^S[R+1]となるiの数(S[i]^A[i]の登場回数))を加算すればよい。

同様に[L+1,R],[L,R-1]の値も計算できる。

あとはクエリを並べ替え、区間を伸び縮みさせる数を減らして行こう。
このように区間の伸び縮みが容易なクエリ群に対しては定番のテクがある(Mo's Algorithmと呼ばれているらしい?)。

クエリをfloor(L/√N)昇順でfloor(L/√N)が一致するものはR順に並べ替えよう。
すると１回のクエリあたり区間の左端Lを動かす量は平均O(√N)となることが期待できる。
また区間の右端は基本的に右に動かすだけで、前のクエリと比べfloor(L/√N)が異なるときだけ左に戻すので、左に戻す回数はO(√N)であることが期待できる。
よってLもRも動かす回数はO(N√N)程度動かせばよい。

int N,M,K;
int A[101010];
int LL[101010],RR[101010];
int L[101010],R[101010];
ll ret[101010];

int NL[2020200];
int NR[2020200];

vector<pair<pair<int,int>,int>> ev;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,N) {
		cin>>A[i];
		if(i) LL[i]=LL[i-1]^A[i-1];
		RR[i]=((i?RR[i-1]:0)^A[i]);
	}
	FOR(i,N) RR[i]^=K;
	
	FOR(i,M) {
		cin>>L[i]>>R[i];
		L[i]--;
		R[i]--;
		ev.push_back({{L[i]/2000,R[i]},i});
	}
	
	ll cn=0;
	int cl=0,cr=-1;
	sort(ALL(ev));
	FORR(r,ev) {
		int tl=L[r.second],tr=R[r.second];
		
		while(tl<cl) cl--, NR[RR[cl]]++, cn+=NR[LL[cl]], NL[LL[cl]]++;
		while(cr<tr) cr++, NL[LL[cr]]++, cn+=NL[RR[cr]], NR[RR[cr]]++;
		while(tl>cl) NL[LL[cl]]--, cn-=NR[LL[cl]], NR[RR[cl]]--, cl++;
		while(cr>tr) NR[RR[cr]]--, cn-=NL[RR[cr]], NL[LL[cr]]--, cr--;
		ret[r.second]=cn;
	}
	
	FOR(i,M) cout<<ret[i]<<endl;
}

まとめ

Codeforces以外でこのテク使ったことないな…。