AtCoder ABC #308 (CodeQUEEN 2023 予選) : G - Minimum Xor Pair Query

この特性知らなかった。
https://atcoder.jp/contests/abc308/tasks/abc308_g

問題

整数の多重集合を考える。初期状態ではこの集合は空である。
以下のクエリに順次答えよ。

• 指定された整数を集合に1つ追加する。
• 指定された整数を集合から1つ削除する。
• 集合内の2要素を選んでxorを取るときの最小値を答える。

解法

x＜y＜zの時min(x xor y, y xor z)＜x xor zである。
よってxorを取る候補は、集合をソートした際の隣接要素のみである。

これをもとに、多重集合と、その隣接要素同士のxorの集合をそれぞれ管理すればよい。

int Q;
multiset<int> S;
multiset<int> cand;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>i;
		if(i==3) {
			cout<<*cand.begin()<<endl;
		}
		else {
			cin>>x;
			if(i==1) {
				
				if(S.size()) {
					auto it=S.lower_bound(x);
					if(it==S.begin()) {
						cand.insert(*it^x);
					}
					else {
						auto it2=prev(it);
						if(it==S.end()) {
							cand.insert(*it2^x);
						}
						else {
							cand.erase(cand.find(*it^*it2));
							cand.insert(*it^x);
							cand.insert(*it2^x);
						}
					}
				}
				S.insert(x);
				
				
			}
			else {
				auto it=S.find(x);
				if(S.size()>1) {
					if(it==S.begin()) {
						cand.erase(cand.find(x^*next(it)));
					}
					else if(next(it)==S.end()) {
						cand.erase(cand.find(x^*prev(it)));
					}
					else {
						cand.erase(cand.find(x^*next(it)));
						cand.erase(cand.find(x^*prev(it)));
						cand.insert(*next(it)^*prev(it));
					}
				}
				S.erase(it);
			}
		}
	}
}

まとめ

もっと面倒な手順を取ろうとしてTLEしてた…。