AtCoder ABC #274 (キーエンスプログラミングコンテスト2022) : Ex - XOR Sum of Arrays

公式解説よりももうちょいお手軽な手順でも解ける？
https://atcoder.jp/contests/abc274/tasks/abc274_h

問題

同じ長さの整数列B,Cに対し、整数列S(B,C)はS(B,C)[i]=B[i] xor C[i]を意味する。
N要素の整数列Aに対し、以下のクエリに答えよ。

• 区間[a,b]、[c,d]、[e,f]が与えられる。S(A[a...b],A[c...d])はA[e...f]より辞書順で小さいか判定せよ。

解法

(AtCoder上では通るが衝突するケースがあるので見直し中)

以下の性質を満たす、Aの区間に対するハッシュ関数が欲しい。

• 区間に対し、高速に計算できる。
• 2つの部分列B,Cに対し、S(B,C)のハッシュ値がBとCのハッシュ値から簡単に計算できる。

以下のハッシュ関数を考える。
H(a,b,i,p) := A[a...b]のうち、x-a≡i (mod p)であるようなA[i]のxorを取った値
これは、A[i]をp間隔で累積xorを取った数列があれば高速に処理できる。

A[a..b]のハッシュ値G(A[a..b])を、以下のような数列で表現しよう。
[H(a,b,0,2),H(a,b,1,2),H(a,b,0,3),H(a,b,1,3),,H(a,b,2,3),H(a,b,0,5)...,H(a,b,16,17)]
つまり、pには2～17の素数、iにはp未満の非負整数となる場合のH(a,b,i,p)を並べた数列である。
この時、G(A[a..b])[i] xor G(A[c..d])[i] = G(S(A[a..b],A[c..d]))[i]となり、欲しいハッシュ関数を満たす。
このハッシュ関数を用いて、S(A[a...b],A[c..d])とA[e...f]のうち先頭何要素が等しいかを二分探索すれば、その次の要素を見ることで数列の大小関係を判定できる。

補足：今回このコードで通ったけど、ハッシュ値衝突させようとすると衝突する様子。高確率で通すコードにするなら、使う素数を増やすとかランダムで切り替えるとか工夫がいるね。

int N,Q;
ll V[505050];
ll S[505050][7];

vector<int> P={2,3,5,7,11,13,17};

vector<ll> myhash(int A,int L) {
	vector<ll> R;
	int i,j;
	FOR(i,P.size()) {
		FOR(j,P[i]) {
			int x=A+j;
			int y=(L-j+P[i]-1)/P[i];
			R.push_back(S[x][i]^S[x+y*P[i]][i]);
		}
	}
	return R;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>V[i];
	for(i=N-1;i>=0;i--) {
		FOR(j,P.size()) S[i][j]=S[i+P[j]][j]^V[i];
	}
	
	FOR(i,Q) {
		int A,B,C,D,E,F,L;
		cin>>A>>B>>C>>D>>E>>F;
		A--,C--,E--;
		L=min(B-A,F-E);
		vector<ll> a=myhash(A,L);
		vector<ll> b=myhash(C,L);
		vector<ll> c=myhash(E,L);
		FOR(j,a.size()) if((a[j]^b[j])!=c[j]) break;
		if(j==a.size()) {
			if(B-A<F-E) {
				cout<<"Yes"<<endl;
			}
			else {
				cout<<"No"<<endl;
			}
			continue;
		}
		int len=0;
		for(j=20;j>=0;j--) if(len+(1<<j)<L) {
			int tmp=len+(1<<j);
			vector<ll> a=myhash(A,tmp);
			vector<ll> b=myhash(C,tmp);
			vector<ll> c=myhash(E,tmp);
			FOR(x,a.size()) if((a[x]^b[x])!=c[x]) break;
			if(x==a.size()) len=tmp;
		}
		if((V[A+len]^V[C+len])<V[E+len]) {
			cout<<"Yes"<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
	}
}

まとめ

Nim Product、勉強しておくか…。