AtCoder ARC #092 : D - Two Sequences

これ500pt…？
https://beta.atcoder.jp/contests/arc092/tasks/arc092_b

問題

N要素の２つの数列A,Bが与えられる。
C(i,j) = A[i]+B[j]とするとき、C(0,0)～C(N-1,N-1)のN^2個の要素のxorを取った値を求めよ。

解法

C(0,0)～C(N-1,N-1)のxorを求める問題なので、各値の2進数表記においてビット毎にそのビットが立っている数の偶奇を求めよう。

今下からp bit目を考える。
A[i]を固定したとき、A[i]+B[j]のp bit目が立つ条件を考えると、A[i]の下位p bitとB[j]の下位 pbitを足すと2^(p-1)以上2^p未満、もしくは*1以上2^(p+1)未満のいずれかである。
よって、B[j]の下位p bitをソートした配列を先に作っておくと、A[i]の下位p bitを用いて配列のlower_boundを用いて、和が上記の範囲に入るものを数え上げることができる。
これでO(NlogN * log(max(A,B))で済む。
なお、lower_boundの部分はA[i]の下位 pbitを先にソートしておくと尺取り法に置き換えることができ、もう少し高速化できる。

int N;
int A[202020];
int B[202020];
int C[602020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	
	int ret=0;
	FOR(i,29) {
		FOR(x,N) C[x]=B[x]&((1<<(i+1))-1);
		sort(C,C+N);
		FOR(x,2*N) C[N+x]=C[x]+(1<<(i+1));
		ll tot=0;
		FOR(x,N) {
			y=A[x]&((1<<(i+1))-1);
			tot += lower_bound(C,C+3*N,(4<<i)-y)-lower_bound(C,C+3*N,(3<<i)-y);
		}
		if(tot%2) ret+=1<<i;
	}
	
	cout<<ret<<endl;
	
}

まとめ

本番割とTLE怖かった。

*1:2^p)+(2^(p-1