Codeforces #367 Div2 D. Vasiliy's Multiset

どうもtrieに慣れない。
http://codeforces.com/contest/706/problem/D

問題

初期状態で整数からなるの空のmultiset Aがある。
これに対し以下の３種類からなるクエリをQ個処理せよ。

• Aに整数xを1つ加える
• Aから整数xを1つ取り除く
• 整数xに対し、y∈A, max(x xor y)の値を答えよ。

解法

AをTrieで管理し、３つ目のクエリに対してはxの上のbitから見ていって、各bitが反転しているyが存在するなら(それはxorを取るとそのbitが1になるので)そちら側のyを選ぶ、ということをしていけば良い。
ただ、自分はあまりTrieに慣れていないので、登場する整数群を座標圧縮し、BITで対応する整数レンジに各bitが反転しているyが1個でも存在するか見ていった。

やっていることは本質的には同じ。
(各bitが反転しているyをどう探すかの違い)

int N;
char C[202020];
int X[202020];
vector<int> V;
map<int,int> M;

int one[202020][32];
int sz[202020][32];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bt;

void dfs(int d,int s,int e) {
	int i;
	if(s==e) return;
	if(d<0) return;
	sz[s][d]=e-s;
	for(i=s;i<e;i++) if(V[i] & (1<<d)) break;
	one[s][d]=i;
	dfs(d-1,s,i);
	dfs(d-1,i,e);
}
int dfs2(int d,int s,int e,int x) {
	int i;
	
	if(e-s==1) return s;
	int zerofirst=(x & (1<<d))>0;
	
	if(zerofirst) {
		if(bt(one[s][d])-bt(s)) return dfs2(d-1,s,one[s][d],x);
		return dfs2(d-1,one[s][d],e,x);
	}
	else {
		if(bt(e)-bt(one[s][d])) return dfs2(d-1,one[s][d],e,x);
		return dfs2(d-1,s,one[s][d],x);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	V.push_back(0);
	FOR(i,N) {
		cin>>C[i]>>X[i];
		V.push_back(X[i]);
	}
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	FOR(i,V.size()) M[V[i]]=i;
	
	dfs(30,0,V.size());
	
	bt.add(1,1);
	
	FOR(i,N) {
		if(C[i]=='+') bt.add(M[X[i]]+1,1);
		else if(C[i]=='-') bt.add(M[X[i]]+1,-1);
		else {
			int y = dfs2(30,0,V.size(),X[i]);
			cout<<(V[y]^X[i])<<endl;
		}
	}
}

まとめ

Trieっていうとどうしても文字列を思い浮かべてしまう。