Codeforces #837 : Div2 F. Hossam and Range Minimum Query

Eまではかなり順調だったのに、Fで手間取った。
https://codeforces.com/contest/1771/problem/F

問題

整数列Aが与えられる。
以下のクエリに順次答えよ。
区間[L,R]が与えられる。A[L],A[L+1],...,A[R]に現れる数値のうち、奇数回登場するものの最小値を求めよ。

なお、前のクエリに答えないと次のクエリが与えられない。

解法

オンラインクエリな問題なので、Mo's Algorithmは使えない。
T[i]を、A[0]～A[i-1]のうち奇数回現れるものを含む永続Trieとする。
T[L-1]とT[R]を同時に探索し、片方にしか現れない最小要素を求めればよい。

なお、Trieにおいては各整数値に対応するハッシュ値を割り当てそのxorをとることで、Subtree内に現れる整数の要約を作ることができる。
これにより、Trieのノードの内容が等しいかどうか高確率で正しく判定できる。

int N,Q;
int A[202020];
ll H[202020];


std::random_device rnd;
std::mt19937 mt(rnd());

vector<int> As;
int nex;
int root[202020];
int L[202020<<5],R[202020<<5];
ll val[202020<<5];

int add(int cur,int CL,int CR,int V,ll XV) {
	int ncur=nex++;
	val[ncur]=val[cur];
	L[ncur]=L[cur];
	R[ncur]=R[cur];
	
	if(CL+1==CR) {
		val[ncur]^=XV;
	}
	else {
		int CM=(CL+CR)/2;
		if(V<CM) {
			L[ncur]=add(L[ncur],CL,CM,V,XV);
		}
		else {
			R[ncur]=add(R[ncur],CM,CR,V,XV);
		}
		val[ncur]=val[L[ncur]]^val[R[ncur]];
	}
	
	return ncur;
}
int get(int cur1,int cur2,int CL,int CR) {
	if(CL+1==CR) {
		if(val[cur1]^val[cur2]) return As[CL];
		else return 0;
	}
	int CM=(CL+CR)/2;
	
	if(val[L[cur1]]^val[L[cur2]]) return get(L[cur1],L[cur2],CL,CM);
	return get(R[cur1],R[cur2],CM,CR);
}




void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	root[0]=nex++;
	cin>>N;
	As.push_back(0);
	FOR(i,N) {
		cin>>A[i];
		As.push_back(A[i]);
		H[i+1]=mt();
	}
	sort(ALL(As));
	As.erase(unique(ALL(As)),As.end());
	FOR(i,N) {
		A[i]=lower_bound(ALL(As),A[i])-As.begin();
		root[i+1]=add(root[i],0,As.size(),A[i],H[A[i]]);
	}
	
	cin>>Q;
	int ans=0;
	while(Q--) {
		int L,R;
		cin>>L>>R;
		L=(L^ans)-1;
		R=(R^ans);
		ans=get(root[L],root[R],0,As.size());
		cout<<ans<<"\n";
	}
	
}

まとめ

このアイデアは賢いな…。