Codeforces #626 Div1 B. Present

どこかで出てそうな問題。
https://codeforces.com/contest/1322/problem/B

問題

N個の正整数列が与えられる。
2要素の和全通りについて、xorを取ったときの値を答えよ。

解法

2要素の和において、各ビットが奇数回登場するかどうかを判定しよう。
今、p bit目の和の偶奇を考えることにする。
各要素についてp bit目以下だけ残した数列を考え、ソートすると、各要素についてペアにしたとき和のp bit目が1になる要素数を二分探索で求められる。

int N;
int A[401010];
int B[401010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	int ret=0;
	FOR(i,28) {
		FOR(j,N) B[j]=A[j]&((1<<(1+i))-1);
		sort(B,B+N);
		ll num=0;
		FOR(j,N) {
			if((B[j]&(1<<i))==0) {
				int L=(1<<i)-B[j];
				int R=(2<<i)-B[j];
				y=lower_bound(B+j+1,B+N,R)-B;
				x=lower_bound(B+j+1,B+N,L)-B;
				//cout<<"!"<<i<<j<<" "<<B[j]<<" "<<L<<" "<<R<<" "<<x<<" "<<y<<endl;
				num+=y-x;
			}
			else {
				int R=(3<<i)-B[j];
				y=lower_bound(B+j+1,B+N,R)-B;
				//cout<<"!"<<i<<j<<" "<<B[j]<<" "<<R<<" "<<y<<endl;
				num+=N-y;
			}
		}
		/*
		cout<<i<<" "<<num<<" "<<ret<<endl;
		FOR(j,N) cout<<B[j]<<" ";
		cout<<endl;
		*/
		if(num&1) ret^=1<<i;
	}
	cout<<ret<<endl;
	
}

まとめ

O(NlogN * maxA)かかるのでちょっと重い。