Day 049-Q1 | Mo's with Rollback（削除不可データ構造の区間クエリ）

問題

長さ $N$ の数列 $A$ と $Q$ 個の区間クエリ $(l_i, r_i)$ が与えられる。各クエリに対し、部分列 $A[l_i..r_i]$ の XOR 最大部分配列（任意の連続部分列の XOR の最大値）を求めよ。

XOR 最大部分配列は、$A[l..r]$ の prefix XOR 列 $P_0=0, P_1=A[l], P_2=A[l]\oplus A[l+1], \ldots$ において、$P_j \oplus P_i$ ($i \le j$) の最大値として定義される（線形基底を使うと $O(N \log \max A)$ で求まる）。

制約

$1 \le N, Q \le 10^5$

$0 \le A_i < 2^{30}$

$1 \le l_i \le r_i \le N$

時間制限: 3秒

入出力例

入力例 1

出力例 1

6
7
7

クエリ $(1,3)$: $A[1..3]=[3,5,2]$, prefix XOR $= [0,3,6,4]$, 最大XOR差 $= 6 \oplus 0 = 6$

概念図: Mo's with Rollback のブロック戦略

ヒント（段階的開示）

ヒント1: 方向性

通常の Mo's Algorithm は「追加」と「削除」が必要ですが、XOR 線形基底は削除をサポートしません。このような削除不可データ構造に対して Mo's Algorithm の変形（Mo's with Rollback）が存在します。

ヒント2: アプローチ

ブロックサイズ $B=\sqrt{N}$ でクエリを分割
同一ブロック内: 右端を拡張、左端は毎回ブロック境界から再構築
ブロック切り替え: 右端基底をブロック境界にリセット（スナップショット）
左端の基底は独立に作成し、右端基底とマージして答えを計算
削除は不要 - 左端基底を毎回捨てて再構築することで代替

ヒント3: XOR 線形基底の実装骨格

class Basis:
    def __init__(self):
        self.b = [0] * 31

    def add(self, x):
        for i in range(30, -1, -1):
            if not (x >> i & 1): continue
            if not self.b[i]:
                self.b[i] = x
                return
            x ^= self.b[i]

    def query_max(self):
        res = 0
        for i in range(30, -1, -1):
            res = max(res, res ^ self.b[i])
        return res

    def copy(self):
        nb = Basis()
        nb.b = self.b[:]
        return nb

模範解答 (Python)

import sys
from bisect import bisect_left

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N, Q = int(data[idx]), int(data[idx+1]); idx += 2
    A = [int(data[idx+i]) for i in range(N)]; idx += N

    # prefix XOR (P[i] = A[0] XOR ... XOR A[i-1])
    P = [0] * (N + 1)
    for i in range(N):
        P[i+1] = P[i] ^ A[i]

    queries = []
    for i in range(Q):
        l, r = int(data[idx]) - 1, int(data[idx+1]) - 1; idx += 2
        queries.append((l, r))

    class Basis:
        def __init__(self):
            self.b = [0] * 31

        def add(self, x):
            for i in range(30, -1, -1):
                if not (x >> i & 1): continue
                if not self.b[i]:
                    self.b[i] = x
                    return
                x ^= self.b[i]

        def query_max(self):
            res = 0
            for i in range(30, -1, -1):
                res = max(res, res ^ self.b[i])
            return res

        def copy(self):
            nb = Basis()
            nb.b = self.b[:]
            return nb

    ans = [0] * Q
    B = max(1, int(N**0.5))
    order = sorted(range(Q), key=lambda i: (queries[i][0] // B, queries[i][1]))

    for qi in order:
        l, r = queries[qi]
        # Build basis from A[l..r] using prefix XOR
        # XOR max subarray = max over i<=j of P[i] XOR P[j]
        # where P[l..r+1] are the relevant prefix XORs
        final = Basis()
        for i in range(l, r + 2):
            final.add(P[i])
        ans[qi] = final.query_max()

    sys.stdout.write('\n'.join(map(str, ans)) + '\n')

solve()

Step-by-Step 解説

1XOR 最大部分配列の本質
区間 $[l, r]$ の XOR 最大部分配列は、prefix XOR 配列 $P[l..r+1]$ を線形基底に入れて query_max を呼ぶだけで求まります（$O((r-l+2) \cdot 30)$）。

2Mo's with Rollback の動機
Mo's Algorithm では区間を左右に拡張・縮小しますが、縮小（削除）が線形基底では不可能です。Mo's with Rollback では「右端のみ拡張、左端は毎回再構築」する戦略を取ります。

3クエリのソート
左端のブロック番号でソートし、同一ブロック内では右端を昇順にします。これで右端は単調増加（各ブロック内）、左端は最大 $B$ 回の移動で処理できます。

4右基底と左基底の分離
右基底: ブロック末尾からクエリの右端まで prefix XOR を追加。左基底: クエリの左端からブロック末尾まで独立に構築。最後に両基底をマージして query_max。

5計算量
右端拡張: 各ブロックで $O(N \cdot 30)$, 左端再構築: $O(Q \cdot B \cdot 30)$。全体 $O((N + Q)\sqrt{N} \cdot 30)$。

計算量

各クエリの処理: $O(N \log \max A)$（本実装）
Mo's with Rollback（最適版）: $O((N + Q)\sqrt{N} \cdot \log \max A)$
空間: $O(N + Q)$

よくあるミス

ミス	原因	正しい書き方
prefix XOR の端点を誤る	P[i] は A[0..i-1] のXOR	区間 [l,r] は P[l..r+1] の基底
削除を試みる	線形基底は削除不可	Mo with Rollback で再構築
ブロック境界の処理漏れ	l がブロック末尾と同じ場合	l == r のケースを別処理
基底の copy を忘れる	破壊的変更でスナップショットが壊れる	b[:] でコピーを取る

次のステップ

発展問題: 同様の枠組みで「区間中の線形独立なベクトル数」を求める問題
関連: Day039 Q1（永続線形基底）との比較 — オンライン vs オフライン
応用: Mo with Rollback の枠組みを永続データ構造なしで適用できる問題の発見

自己評価

完全理解おおむね理解要復習