Codeforces #1123 : Div2. F2. XOR Transformations (Hard Version)

これライブラリ化してなかったな…。
https://codeforces.com/contest/2267/problem/F2

問題

M要素の数列Bがあるとき、f(B)は以下のように作られる。

• B[i] xor B[j]を列挙した数列Cを作り、それを昇順にソートして専用M要素を取ったもの

N要素の整数列Aが与えられる。
クエリとして整数Xが与えられる。f^X(A)における最大値と最小値の差を答えよ。

解法

Nが5以上なので、f(f(A))のようにfを２回適用すると、max(A)のMSBはなくなる。
よって、O(log(max(A)))回fを適用すると、Aはゼロになる。実際には、今回の問題の範囲では9回行えばゼロになる様子。

あとはf(A)を9回まで求めよう。
Trieを作り、
g(v,n) := Aのうち、vとのxorを取ったものの値が小さい順にn番目
となるg(v,n)を求めよう。
priority queueにg(A[i],n)を入れて順次小さい順にN個まで取り出すようにすればf(A)を構築できる。

struct BinaryXorTrie {
	BinaryXorTrie *nex[2];
	ll v;
	BinaryXorTrie() {
		nex[0]=nex[1]=NULL;v=0;
	}
	void add(ll s,ll a=1,int pos=59) {
		v+=a;
		if(pos<0) return;
		int c=(s>>pos)&1;
		if(!nex[c]) nex[c]=new BinaryXorTrie();
		nex[c]->add(s,a,pos-1);
	}
	// mask ^ vが小さい方からrank番目のものをとる
	ll pick(ll mask,int rank,int pos=59) {
		if(pos<0) {
			return 0;
		}
		if(v<rank) return -1;
		
		int ismax=0; //minじゃなくmax
		if(((mask&(1LL<<pos))>0)^ismax) {
			if(nex[1]) {
				if(rank<=nex[1]->v) return (1LL<<pos)+nex[1]->pick(mask,rank,pos-1);
				rank-=nex[1]->v;
			}
			return nex[0]->pick(mask,rank,pos-1);
		}
		else {
			if(nex[0]) {
				if(rank<=nex[0]->v) return nex[0]->pick(mask,rank,pos-1);
				rank-=nex[0]->v;
			}
			return (1LL<<pos)+nex[1]->pick(mask,rank,pos-1);
		}
	}
};

int T,N,Q;
int A[202020],X;
int C[202020];
BinaryXorTrie bxt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>Q;
		FOR(i,N) {
			cin>>A[i];
		}
		sort(A,A+N);
		
		map<int,int> M;
		int num=0;
		while(1) {
			M[num]=A[N-1]-A[0];
			if(A[N-1]==0) break;
			
			priority_queue<pair<ll,int>> Q;
			FOR(i,N) {
				bxt.add(A[i],1);
			}
			FOR(i,N) {
				Q.push({-(A[i]^bxt.pick(A[i],2)),i});
				C[i]=2;
			}
			vector<int> V;
			FOR(i,2*N) {
				auto p=Q.top();
				Q.pop();
				x=p.second;
				V.push_back(-p.first);
				C[x]++;
				if(C[x]<=N) {
					Q.push({-(A[x]^bxt.pick(A[x],C[x])),x});
				}
			}
			FOR(i,N) {
				bxt.add(A[i],-1);
				A[i]=V[i*2];
			}
			num++;
		}
		
		while(Q--) {
			cin>>x;
			cout<<M[x]<<endl;
		}
	}
}

まとめ

手元に最小値を取るTrieしかなかったので、この機会にライブラリを整備した。