この問題は Rolling Hash と呼ばれる列のハッシュアルゴリズムを応用すれば解ける問題です。まずは Rolling Hash を詳しく見ていきましょう。

Rolling Hash とは？

ハッシュ とは、あるデータ \(d\) および ハッシュ関数 \(\text{hash}\) があったときの \(\text{hash}(d)\) の値のことを言います。(ここで \(\text{hash}(d)\) は \(d\) より情報量が小さい) ハッシュは主に巨大なデータ同士が一致しているのかを判定するのに利用されます。

例えば長さ \(N\) の数列 \(A\) と数列 \(B\) があったとき、\(A\) と \(B\) が一致しているか判定する問題を考えてみましょう。これは愚直にやろうとすると \(\mathrm{O}(N)\) かかってしまいますが、あらかじめ \(\text{hash}(A)\) と \(\text{hash}(B)\) (どちらも \(64\) bit に収まる整数とします) を計算していれば 、\(A\) と \(B\) の一致判定は \(\mathrm{O}(1)\) で行うことができます。

Rolling Hash とは、列のハッシュを高速に計算できるハッシュアルゴリズムです。
数列 \(A = (A_1, A_2, \dots, A_N)\) が与えられたときに、ハッシュ関数 \(R\) を次のように定義します。(ここで \(p\) は十分大きい素数, \(x\) は \([0, p)\) から 実行時に一様ランダムに選んだ整数 です。) このようなハッシュ関数を Rolling Hash と呼びます。

\[R(A) = \left(\sum_{i=1}^N A_i x^{N-i} \right) \bmod{p}\]

ローリングハッシュはいくつかのよい性質を持ちます。
1 つは、\(\mathrm{O}(N)\) の前計算を行えば \(A\) の任意の部分列 \(A(a, b)\) のハッシュを \(\mathrm{O}(1)\) で求められる点です。 (\(\text{mod }p\) 上の演算が \(\mathrm{O}(1)\) でできると仮定しています) まず、

\[R(A(1, 1)) = A_1, R(A(1, n)) = R(A(1, n-1)) \times x + A_n (n \gt 1)\]

という漸化式から \(A(1, 1), A(1, 2),\dots, A(1, N)\) のハッシュを \(\mathrm{O}(N)\) で列挙しておきます。また、 \(x^1, x^2,\dots,x^N\) もあらかじめ \(\mathrm{O}(N)\) で求めておきます。

すると、\(A(a, b)\) のハッシュは

\[R(A(a, b)) = R(A(1, b)) - R(A(1,a-1)) \times x^{b-(a-1)}\]

と、あらかじめ前計算した値の式として表せるというわけです。

もう一つはハッシュの 衝突耐性 です。 ハッシュ関数 \(H\) および 数列 \(A, B\) について \(A \neq B\) かつ \(H(A) = H(B)\) が成り立つ時、\(A\) と \(B\) のハッシュが 衝突 していると呼びます。
ハッシュ関数の重要な性質として、「\(A, B\) であって \(H(A) \neq H(B)\) を満たすような \(A, B\) が簡単に見つからない」という性質が必要です。なぜならば、そのような \(A, B\) が簡単に見つかってしまうと、プログラムは悪意を持った人(プログラミングコンテストでは作問者)にそのような \(A, B\) を比較させられて「\(H(A) = H(B)\) だから \(A = B\) だ！」と誤判定してしまうからです。このような性質を衝突耐性と呼びます。

例として、よくないハッシュとしてハッシュ関数 \(H\) を \(H(A) = A_1 + A_2 + \dots + A_N\) を挙げます。このハッシュは \(A\) の要素がランダムである場合は有効に機能しますが、作問者があらかじめ \(H\) を使う人がいるのを想定して \(A = (2, 7, 4), B = (1, 4, 8)\) を比較するテストケースを入れると 100 % 衝突して誤答を返すので、これはよくないハッシュです。

プログラミングコンテストにおいて解法として利用するハッシュ関数は、基本的に次の性質を満たす必要があります。

• 作問者がどれだけ悪意に満ちたテストケースを入れてきたとしても、非常に高い確率でハッシュ衝突が発生しない

Rolling Hash はそのような条件を満たすことが数学的に証明されています。

長さ \(N\) の相異なる数列 \(A, B\) のハッシュが衝突しているとします。このとき次の式が成り立ちます。

\[H(A) = H(B) \iff \sum_{i=1}^N x^{N-i} (A_i - B_i) \equiv 0 \pmod{p}\]

左辺は \(\text{mod }p\) 上の \(x\) の \(N-1\) 次多項式なので、そのような \(x\) は高々 \(N-1\) 個しか存在しません。また、\(x\) は前にも書いた通り「 実行時に一様ランダムに選んだ整数 」なので、作問者がプログラムの選ぶ \(x\) を狙い撃ってハッシュを衝突させにいくこともできません。よって、\(N \ll p\) ならば Rolling Hash は非常に高い確率で衝突しないハッシュ関数であると言えます。

\(\text{XOR}\) が \(+\) に置き換わった場合の解法

まず、\(S(B,C)\) の \(\text{XOR}\) の部分が \(+\) に置き換わった場合、すなわち

\[S(B, C) = (B_1+C_1, B_2+C_2, ..., B_{|B|} + C_{|B|})\]

である場合を解いてみましょう。

列のハッシュ関数 \(H\) を Rolling Hash で定義します。このとき、長さが等しい列 \(B,C\) に対して

\[H(S(B,C)) = H(B) + H(C)\]

が成り立つので、\(H(S(B,C))\) は \(H(B)\) と \(H(C)\) と同じ計算量 (すなわち \(\mathrm{O}(1)\)) で求まります。

上の事実を利用すればこの問題は容易に解くことができます。まず、適切な \(\mathrm{O}(N)\) の前計算により任意の \(a\leq b\) について \(A(a, b)\) のハッシュを \(\mathrm{O}(1)\) で求められるようにします。そして、各クエリ \((a,b,c,d,e,f)\) に対しては \(S(H(a,b), H(c,d))\) と \(S(e,f)\) の LCP を二分探索 + ハッシュで \(\mathrm{O}(\log N)\) で求められるので、それを利用すれば \(\mathrm{O}(\log N)\) で答えを求められます。

よって全体の計算量は \(\mathrm{O}(N + Q \log N)\) でこの問題を解くことができます。ハッシュが衝突する確率は、全体で長さ \(N\) の列を \(\mathrm{O}(Q \log N)\) 回比較しているので高々 \(N Q \log N / p\) で抑えられます。\(p \sim 10^{18}\) としたとき \(N Q \log N / p \sim 10^{-6}\) で、これは十分小さいです。 (きちんと評価すると \(NQ / p\) になるような気がしますがここでは割愛します)

元の問題への適用

さて、元の問題に戻りましょう。

\[S(B, C) = (B_1 \oplus C_1, B_2 \oplus C_2, ..., B_{|B|} \oplus C_{|B|})\]

である場合でも上の解法を適用するには、次の条件を満たすようなハッシュを構成する必要があります。

• \(H(S(B,C)) = H(B) \oplus H(C)\) が成り立つ
• 適切な前計算によって \(H(A(a,b))\) を十分高速に求められる
• 衝突耐性がある

このようなハッシュを構成する方法はいくつか存在しますが、ここでは Nimber を利用した解法を説明します。

Rolling Hash では \(\text{mod }p\) 上の演算を利用してハッシュの値を求めていました。実は、Rolling Hash の「任意の部分列のハッシュを高速に計算出来る」「衝突耐性がある」という性質は、 \(\text{mod }p\) 上の演算が 体 と呼ばれる代数的な構造を取っている事実から示されます。(詳細は略します)

• 参考：可換体(Wikipedia)

そこで、\(\oplus\) が加法になるような体を見つけてきて Rolling Hash に載せることを考えましょう。そのような体が存在すれば、Rolling Hash にその体を載せて上の解法を適用すればこの問題を解くことができます。
Nimber は xor を加法、Nim product を乗法とする体で、この問題にまさにうってつけです。(Nim product が競技プログラミングに頻出なのもあります)

Nim product と Nimber

Nim product \(\otimes\) とは次のように定義される演算です。

\[a \otimes b := \text{mex} \lbrace (a' \otimes b) \oplus (a \otimes b') \oplus (a' \otimes b') \vert a' \lt a, b' \lt b \rbrace\]

集合 \(A\) を \(0\) 以上 \(2^{2^n}\) (\(n\) は整数) 未満の整数からなる集合として、\(\oplus, \otimes\) を \(A\) 上で定義される演算とします。このとき \(\oplus\) を加法, \(\otimes\) を乗法とする代数的構造は体になることが知られています。 このような体を Nimber と呼びます。

よって、 Rolling Hash 上に Nimber を載せれば、Nim product の計算量を \(M\) としてこの問題を \(\mathrm{O}(M (N + Q \log N))\) 程度で解くことができて、ハッシュの衝突確率も \(NQ \log N / 2^{64} \sim 10^{-7}\) と極めて低いです。

• この問題のテストケース数は \(86\) ケースなのでこの解法が WA になる確率は \(1 - (1-10^{-7})^{86} \sim 10^{-5}\) 程度で、これは任意のコンテスタントの一生における提出回数が \(10^4\) ～ \(10^5\) オーダーであることを鑑みると、一生に一度起こるかどうかの十分低い確率であると考えてよいと思います。

また、Nim product は 再帰 + 前計算を利用すれば \(64\) 回程度の前計算テーブルの参照で求めることができて、これは十分高速です。 (詳しくは実装例および kyopro_friends さんの記事 にある再帰の式などを参考にしてください。)

• 実装例 (C++)

#include <cassert>
#include <cstdio>
#include <ctime>
#include <random>
using namespace std;

using u64 = unsigned long long;
constexpr int N_MAX = 1e6 + 10;
int N, Q;
u64 A[N_MAX], pw[N_MAX], hs[N_MAX], basis, small[256][256];

template <bool is_pre = false>
u64 nim_product(u64 a, u64 b, int p = 64) {
  if (min(a, b) <= 1) return a * b;
  if (!is_pre and p <= 8) return small[a][b];
  p >>= 1;
  u64 a1 = a >> p, a2 = a & ((1ull << p) - 1);
  u64 b1 = b >> p, b2 = b & ((1ull << p) - 1);
  u64 c = nim_product<is_pre>(a1, b1, p);
  u64 d = nim_product<is_pre>(a2, b2, p);
  u64 e = nim_product<is_pre>(a1 ^ a2, b1 ^ b2, p);
  return nim_product<is_pre>(c, 1uLL << (p - 1), p) ^ d ^ ((d ^ e) << p);
}

void init() {
  for (int i = 0; i < 256; i++)
    for (int j = 0; j < 256; j++) small[i][j] = nim_product<true>(i, j, 8);
  pw[0] = 1, hs[0] = basis = 0;
  mt19937_64 rng(time(NULL));
  basis = rng();
  for (int i = 1; i <= N; i++) {
    pw[i] = nim_product(pw[i - 1], basis);
    hs[i] = nim_product(hs[i - 1], basis) ^ A[i - 1];
  }
}
u64 get(int l, int r) { return nim_product(hs[l], pw[r - l]) ^ hs[r]; }
void send(int flag) { printf(flag ? "Yes\n" : "No\n"); }

int main() {
  scanf("%d %d", &N, &Q);
  for (int i = 0; i < N; i++) scanf("%llu", &(A[i]));
  init();
  while (Q--) {
    int a, b, c, d, e, f;
    scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f);
    --a, --c, --e;
    int l = 0, h = min(f - e, b - a) + 1;
    while (l + 1 < h) {
      int m = (l + h) / 2;
      ((get(a, a + m) ^ get(c, c + m) ^ get(e, e + m)) ? h : l) = m;
    }
    send(e + l != f and (a + l == b or (A[a + l] ^ A[c + l]) < A[e + l]));
  }
}

Nimber を利用して解ける出題例

• yukicoder No.1775 Love Triangle 2
• yosupo さんによる関連記事(AGC 級コンテストの問題のネタバレあり)