TopCoder SRM 753 Div1 Medium MojisBag

これは本番ちょっと自信ないままSubmitしたので、通ってよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=15254

問題

整数のmultiset Sに対し、要素の増減のクエリQ個が与えられる。
クエリ毎に、Sのうち２要素のxorを取った際の最大値を求めよ。(Sが1要素以下なら0とする)

なお、追加・削除のクエリは疑似乱数で生成される。
また、削除クエリが出る確率は1/Rで(1テストケース内では)固定である。

解法

削除クエリが無く追加クエリのみの場合を考える。
常時解となる２要素の対を持っておき、新規要素を追加するとき、その要素と既存の要素のxorを取って最大値を更新できるかその都度判定することを考えよう。
これは定番で、要素を固定長の2進数表記の文字列とみなし、Trieを作って置けば、1回追加するあたりO(log(入力値の最大値))で済む。
全体でO(Q*log(入力値の最大値))なので間に合う。

問題は削除で、最大値を成す２要素の片方が削除されてしまうと、次の最大値を探すのは容易ではない。
追加なら容易にできるだが、全要素を一旦消して、残るものを再度登録しながら上記処理を行うと、その処理だけで1クエリでO(Q*log(入力値の最大値))程度かかってしまう。

だが、ここで入力が疑似乱数であることに着目しよう。

• Rが大きい場合、削除クエリはめったにない。また、仮に削除クエリが発生しても、その場合その分追加クエリが多いので、最大値を成す２要素のいずれかが消されることはもっとめったにない。
  • なので、上記全削除+再登録はほとんど起きないので、やってしまってもよい。
• Rが小さい場合、逆に要素がどんどん消されるので、残される要素は少ない。
  • なので、上記全削除+再登録の手間は小さいので、やってしまってもよい。

ということで、削除の場合は全削除+再登録をやってしまってもよい。

ll X[101010],Y[101010],Z[101010];
int id[101010];
ll mo=1000000007;
vector<ll> added;
set<int> valid;

struct BinarySumTrie {
	BinarySumTrie *nex[2];
	ll v;int num;
	set<int> S;
	BinarySumTrie() {
		nex[0]=nex[1]=NULL;v=0;num=0;
	}
	void add(int s,int id,int flag,int pos=29) {
		if(flag) num++;
		else num--;
		if(pos>=0) {
			int c=(s>>pos)&1;
			if(!nex[c]) nex[c]=new BinarySumTrie();
			nex[c]->add(s,id,flag,pos-1);
		}
		else {
			v=s;
			if(flag) S.insert(id);
			else S.erase(id);
		}
	}
	pair<int,int> pick(int mask,int pos=29) {
		if(pos<0) {
			return {v,*S.begin()};
		}
		
		if(mask&(1<<pos)) {
			if(nex[0] && nex[0]->num) return nex[0]->pick(mask,pos-1);
			return nex[1]->pick(mask,pos-1);
		}
		else {
			if(nex[1] && nex[1]->num) return nex[1]->pick(mask,pos-1);
			return nex[0]->pick(mask,pos-1);
		}
	}
};

class MojisBag {
	public:
	int maximumXor(int Q, int base, int add, int rate) {
		ZERO(Y);
		ZERO(Z);
		added.clear();
		valid.clear();
		
		
		BinarySumTrie* root=new BinarySumTrie();
		
		
		X[0]=add;
		int i;
		pair<int,int> P={-1,-1};
		FOR(i,Q) {
			if(X[i]%rate) {
				added.push_back(X[i]);
				id[i]=added.size()-1;
				
				if(root->num>0) {
					auto p=root->pick(X[i]);
					if(P.first==-1 || (added[P.first]^added[P.second])<(X[i]^p.first)) {
						P={id[i],p.second};
					}
				}
				valid.insert(id[i]);
				root->add(X[i],id[i],1);
			}
			else if(added.size()) {
				int idx=X[i]%added.size();
				if(valid.count(idx)) {
					valid.erase(idx);
					root->add(added[idx],idx,0);
					if(P.first==idx || P.second==idx) {
						P.first=P.second=-1;
						FORR(v,valid) root->add(added[v],v,0);
						FORR(v,valid) {
							if(root->num>0) {
								auto p=root->pick(added[v]);
								if(P.first==-1 || (added[P.first]^added[P.second])<(added[v]^p.first)) {
									P={v,p.second};
								}
							}
							root->add(added[v],v,1);
						}
					}
				}
			}
			if(P.first!=-1) Y[i]=added[P.first]^added[P.second];
			Z[i+1]=(Z[i]*base+Y[i])%mo;
			X[i+1]=(X[i]*base+add)%mo;
		}
		
		return Z[Q];
		
	}
}

まとめ

これ自信を持ってSubmitできる気しないな。