Codeforces #880 : Div1 C. Twin Clusters

これもコードが短め。
https://codeforces.com/contest/1835/problem/C

問題

2^(K+1)要素の整数列Gが与えられる。
各値は4^K未満の非負整数である。

Gの空でなく共通部分を持たない部分列を2個選び、それぞれのxorの値が一致するようにしたい。
可能ならその一例を示せ。

解法

Gのprefix xorであるSを考える。
Sのうち、下位K bitが一致するペアを探そう。
そのうち、上位K bitの差が一致する2つのペアを見つけ、その4つのindexを昇順にa,b,c,dとするなら、[a,b],[c,d]となる2つの閉区間が解となる。

int K,T;
ll S[2<<19];
int hi[1<<19];
pair<int,int> lo[1<<19];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>K;
		int N=1<<(K+1);
		FOR(i,N) {
			cin>>S[i+1];
			S[i+1]^=S[i];
			hi[i]=-1;
			lo[i]={-1,-1};
		}
		hi[0]=0;
		for(i=1;i<=N;i++) {
			if(hi[S[i]>>K]!=-1) {
				ll dif=(S[hi[S[i]>>K]]^S[i])&((1<<K)-1);
				if(lo[dif].first!=-1) {
					vector<int> A={lo[dif].first,lo[dif].second,hi[S[i]>>K],i};
					sort(ALL(A));
					cout<<A[0]+1<<" "<<A[1]<<" "<<A[2]+1<<" "<<A[3]<<endl;
					break;
					
				}
				else {
					lo[dif]={hi[S[i]>>K],i};
				}
				
			}
			hi[S[i]>>K]=i;
		}
		
		
	}
}

まとめ

これも言われてみるとすんなりなんだけどな。