Day 046-Q1 | XOR線形基底上のランダム射影（Segment Tree + Basis マージ）

問題

$N$ 個の非負整数 $a_1, a_2, \ldots, a_N$（各 $0 \le a_i < 2^{60}$）が与えられる。以下の $Q$ クエリを処理せよ：

1 i x：$a_i$ を $x$ に変更する（1-indexed）
2 l r：$a_l, \ldots, a_r$ の部分集合 XOR で実現可能な最大値を求める

制約

$1 \le N \le 5 \times 10^4$

$1 \le Q \le 5 \times 10^4$

$0 \le a_i < 2^{60}$

$1 \le l \le r \le N$

時間制限: 3秒

入出力例

入力例 1

出力例 1

7
7

概念図: セグメント木上の XOR 線形基底

ヒント（段階的開示）

ヒント1: 方向性

線形基底（XOR Basis）を区間ごとに保持するデータ構造を考えましょう。セグメント木の各ノードに線形基底を持たせると区間クエリが処理できます。

ヒント2: アプローチ

線形基底のマージ: 2つの基底を合成するには一方の要素を他方に挿入すればよい（$O(60^2)$）
セグメント木: 各ノードにその区間の XOR 基底を格納
クエリ: 区間分割して基底をマージ → 最大 XOR を貪欲に読み出す
更新: 対象位置を含む $O(\log N)$ ノードの基底を再構築

ヒント3: 実装骨格

class Basis:
    def __init__(self):
        self.b = []
    def add(self, x):
        for v in self.b:
            x = min(x, x ^ v)
        if x:
            self.b.append(x)
            self.b.sort(reverse=True)
    def max_xor(self, init=0):
        res = init
        for v in self.b:
            res = max(res, res ^ v)
        return res
    @staticmethod
    def merge(b1, b2):
        res = Basis(); res.b = b1.b[:]
        for x in b2.b: res.add(x)
        return res

模範解答 (Python)

import sys
input = sys.stdin.readline

class Basis:
    __slots__ = ('b',)
    def __init__(self):
        self.b = []

    def add(self, x):
        for v in self.b:
            x = min(x, x ^ v)
        if x:
            self.b.append(x)
            self.b.sort(reverse=True)

    def max_xor(self, init=0):
        res = init
        for v in self.b:
            res = max(res, res ^ v)
        return res

    @staticmethod
    def merge(b1, b2):
        res = Basis()
        res.b = b1.b[:]
        for x in b2.b:
            res.add(x)
        return res


def main():
    N, Q = map(int, input().split())
    a = list(map(int, input().split()))

    size = 1
    while size < N:
        size <<= 1
    tree = [Basis() for _ in range(2 * size)]

    def build(i, val):
        pos = size + i
        tree[pos] = Basis()
        tree[pos].add(val)
        pos >>= 1
        while pos >= 1:
            tree[pos] = Basis.merge(tree[2*pos], tree[2*pos+1])
            pos >>= 1

    def query(l, r):  # [l, r] 0-indexed
        res = Basis()
        l += size
        r += size + 1
        while l < r:
            if l & 1:
                res = Basis.merge(res, tree[l])
                l += 1
            if r & 1:
                r -= 1
                res = Basis.merge(res, tree[r])
            l >>= 1
            r >>= 1
        return res.max_xor()

    for i in range(N):
        build(i, a[i])

    out = []
    for _ in range(Q):
        line = list(map(int, input().split()))
        if line[0] == 1:
            i, x = line[1] - 1, line[2]
            a[i] = x
            build(i, x)
        else:
            l, r = line[1] - 1, line[2] - 1
            out.append(query(l, r))
    print('\n'.join(map(str, out)))

main()

Step-by-Step 解説

1線形基底（XOR Basis）の復習
GF(2) 上の線形空間で、集合 $S$ の XOR で作れる全元を基底 $B$ で表現。最大60ビットなら最大60元の基底で十分。要素追加は既存基底で掃き出し、残れば追加 $O(60)$。

2基底のマージ $O(60^2)$
2基底 $B_1, B_2$ のマージは $B_2$ の全要素を $B_1$ に insert するだけ。60要素 × 60ステップ = $O(3600)$。

3セグメント木の構築
各ノードに区間の XOR 基底を格納。葉は単一要素の基底。内部ノードは左右の基底をマージ。

4区間クエリ $O(\log N \cdot 60^2)$
通常のセグメント木クエリと同様に区間を $O(\log N)$ ノードに分割し、基底を順次マージ → 最大XORを貪欲読み出し。

5更新 $O(\log N \cdot 60^2)$
葉を再構築し、祖先を順次 merge で更新。

計算量

構築: $O(N \log N \cdot 60^2)$
更新: $O(\log N \cdot 60^2)$
クエリ: $O(\log^2 N \cdot 60^2)$（最悪 $\log N$ 個のマージ）
空間: $O(N \log N \cdot 60)$

よくあるミス

ミス	原因	正しい書き方
基底ソートを忘れる	最大XOR貪欲が正しく動かない	`self.b.sort(reverse=True)`
マージ時に元の基底を破壊	参照コピーのまま変更	`res.b = b1.b[:]` でコピー
0-indexed/1-indexed ミス	クエリの境界がずれる	入力時に `l-1`, `r-1`
空の基底の max_xor が未定義	空集合のXORは0	`init=0` で問題なし

次のステップ

発展問題: $k$ 番目に大きい XOR 値を求める（基底の rank 利用）
関連: 永続線形基底（Day039 Q1）と組み合わせた区間 XOR k 番目
応用: マトロイドの独立性判定への拡張

自己評価

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