Day 019-Q1 — 線形基底（XOR Basis over GF(2)）

2026-05-02 赤色 Master / Phase 8+ ★★★★★★★★★ 線形基底

問題

$N$ 個の非負整数が与えられる。Q個のクエリに答えよ。

  • クエリ型1: 1 l r — 区間 $[l, r]$ の要素の部分集合 XOR で作れる最大値
  • クエリ型2: 2 l r k — 区間 $[l, r]$ の部分集合 XOR で作れる値のうち $k$ 番目に大きい値

制約

$1 \le N \le 5 \times 10^4$
$0 \le a_i < 2^{30}$
$1 \le Q \le 5 \times 10^4$

入出力例

入力例 1

5
6 5 3 7 2
3
1 1 3
2 1 5 0
2 1 5 3

出力例 1

7
7
4

ヒント (段階的開示)

ヒント1: 方向性
線形代数の考え方をGF(2)（0/1の加算がXOR）上で行う。「基底」を構築すれば部分空間全体を表現できる。
ヒント2: アプローチ
線形基底の構築：各要素を高いビットから挿入し、既存の基底と被るビットがあればXORで消す。区間クエリはマージ可能な性質を利用してセグメント木で処理。
ヒント3: 誘導 
class LinearBasis:
    def insert(self, x):
        for i in range(29, -1, -1):
            if not (x >> i & 1): continue
            if not self.b[i]:
                self.b[i] = x; return
            x ^= self.b[i]

模範解答 (Python)

import sys
input = sys.stdin.readline

class LinearBasis:
    def __init__(self):
        self.b = [0] * 30
        self.rank = 0

    def insert(self, x):
        for i in range(29, -1, -1):
            if not (x >> i & 1): continue
            if not self.b[i]:
                self.b[i] = x; self.rank += 1; return
            x ^= self.b[i]

    def merge(self, other):
        res = LinearBasis()
        res.b = self.b[:]; res.rank = self.rank
        for i in range(29, -1, -1):
            if other.b[i]:
                res.insert(other.b[i])
        return res

    def reduce(self):
        for i in range(29, -1, -1):
            if not self.b[i]: continue
            for j in range(i+1, 30):
                if self.b[j] >> i & 1:
                    self.b[j] ^= self.b[i]
        self.reduced = [self.b[i] for i in range(30) if self.b[i]]

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

    def kth(self, k):
        self.reduce()
        r = self.reduced
        if k >= (1 << len(r)): return -1
        res = 0
        for i, v in enumerate(r):
            if k >> i & 1:
                res ^= v
        return res

def build_seg(a, n):
    size = 1
    while size < n: size <<= 1
    seg = [LinearBasis() for _ in range(2 * size)]
    for i in range(n):
        seg[size + i].insert(a[i])
    for i in range(size - 1, 0, -1):
        seg[i] = seg[2*i].merge(seg[2*i+1])
    return seg, size

def query(seg, size, l, r):
    res = LinearBasis()
    l += size; r += size + 1
    while l < r:
        if l & 1: res = res.merge(seg[l]); l += 1
        if r & 1: r -= 1; res = res.merge(seg[r])
        l >>= 1; r >>= 1
    return res

def main():
    n = int(input())
    a = list(map(int, input().split()))
    seg, size = build_seg(a, n)
    q = int(input())
    for _ in range(q):
        line = list(map(int, input().split()))
        if line[0] == 1:
            _, l, r = line
            b = query(seg, size, l-1, r-1)
            print(b.max_xor())
        else:
            _, l, r, k = line
            b = query(seg, size, l-1, r-1)
            print(b.kth(k))

main()

Step-by-Step 解説

1線形基底の構造
GF(2) 上のベクトル空間。各整数を30ビットのベクトルとみなす。基底は最大30要素で、各要素は他と異なる最高ビット。
2insert 操作 O(30)
ビット29から0に走査。1なら基底に空きがあれば格納、既存と XOR して消去。
3merge 操作
一方の基底のすべての要素を他方に insert するだけ。
4k番目の値
Reduced Form（完全上三角化）に変換すると、kの各ビットが基底のどれを使うかに対応。
5セグメント木統合
各ノードに LinearBasis を持つ。区間クエリは merge で O(log N × 30²)。

よくあるミス

ミス原因正しい書き方
kth で 0 を含まない空の部分集合 XOR = 0 を忘れreduced form の k は 0〜2^rank-1
merge で片方の基底を破壊in-place 操作コピーしてから merge
ランクを数え忘れinsert の return 値を無視rank は正確に管理する

次のステップ

  • 発展: オンラインクエリ（add/query混合）ではオフライン処理か、モノイドとして扱う

自己評価

自分の回答

気づき・メモ