Day 039-Q1 | 永続線形基底（XOR 区間最大値クエリ）

問題

長さ $N$ の整数列 $A$ と $Q$ 個のクエリ。クエリ l r に対して、$A[l..r]$（1-indexed）の部分列から任意個を選んで XOR を取った最大値を求めよ。

制約

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

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

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

時間制限: 3sec / メモリ: 512MB

入出力例

入力例 1

出力例 1

7
5
7

クエリ1: A[1..3]={3,1,4} → 3⊕4=7。クエリ2: A[2..5]={1,4,1,5} → 4⊕1=5。クエリ3: A[1..5] → 3⊕4=7。

概念図: 永続線形基底

各 prefix $[1..i]$ について線形基底を保持。右のインデックスを優先して挿入することでクエリ時に範囲制限が可能。

ヒント（段階的開示）

ヒント1: 方向性

区間 XOR 最大は GF(2) 上の線形基底（Linear Basis）を使う。prefix の基底を保持し、クエリ時に左端以上のインデックスの行のみを使う。

ヒント2: インデックスの優先度

Gauss 消去時に「より右（大きいインデックス）の要素を優先して各ビット位置に配置」する。これにより、basis[b][1] >= l で有効性を判定できる。

ヒント3: 実装骨格

# 挿入時: より右のインデックスを優先
for b in range(BITS-1, -1, -1):
    if not (val >> b & 1): continue
    if basis[b] is None:
        basis[b] = (val, idx); break
    if basis[b][1] < idx:
        val, idx, basis[b] = basis[b][0]^val, basis[b][1], (val, idx)
    else:
        val ^= basis[b][0]

# クエリ時: idx >= l の行のみ使用
res = 0
for b in range(BITS-1, -1, -1):
    if basis[b] and basis[b][1] >= l:
        res = max(res, res ^ basis[b][0])

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))

    BITS = 30
    prefixes = [None] * (N + 1)
    prefixes[0] = [None] * BITS

    for i in range(N):
        basis = list(prefixes[i])
        val = A[i]
        idx = i + 1  # 1-indexed
        for b in range(BITS - 1, -1, -1):
            if not (val >> b & 1):
                continue
            if basis[b] is None:
                basis[b] = (val, idx)
                break
            if basis[b][1] < idx:
                val, idx, basis[b] = basis[b][0] ^ val, basis[b][1], (val, idx)
            else:
                val ^= basis[b][0]
        prefixes[i + 1] = basis

    out = []
    for _ in range(Q):
        l, r = map(int, input().split())
        basis = prefixes[r]
        res = 0
        for b in range(BITS - 1, -1, -1):
            if basis[b] is not None and basis[b][1] >= l:
                if res ^ basis[b][0] > res:
                    res ^= basis[b][0]
        out.append(res)

    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

1線形基底の基礎
GF(2) 上の線形基底はビット $b$ の位置に最上位ビットが $b$ の要素を 1 つ配置する。Gauss 消去法で構築。

2インデックスの優先管理
挿入時に「より右（大きいインデックス）の要素を各ビット位置に優先配置」。押し出された古い要素は再挿入（スワップ）する。

3prefix 配列の構築
各 $i$ について prefixes[i] = A[1..i] の基底（各ビット位置に (value, idx)）を格納。$O(N \cdot B)$。

4クエリ処理
prefixes[r] を参照し、各ビット b で basis[b][1] >= l なら有効行として XOR 最大化に使用。$O(B)$。

5計算量評価
前処理 $O(NB)$、クエリ $O(QB)$、メモリ $O(NB)$。$B = 30$ なので実用的。

計算量

前処理: $O(N \cdot B)$ — $B = 30$ ビット
クエリ: $O(Q \cdot B)$ per query
メモリ: $O(N \cdot B)$（各 prefix の基底配列のシャローコピー）

よくあるミス

ミス	原因	正しい書き方
swap 時の XOR 計算順序ミス	val と basis[b][0] を XOR した後に代入する順序	`val, idx, basis[b] = basis[b][0]^val, basis[b][1], (val, idx)`
0-indexed/1-indexed 混在	クエリの l が 1-indexed	挿入時に `idx = i + 1` で 1-indexed に統一
クエリ時に全基底を無条件使用	区間 [l,r] 制約を無視	`basis[b][1] >= l` の条件を必ず確認
prefix のコピーを忘れる	前の basis を破壊	`basis = list(prefixes[i])` でシャローコピー

Day 039-Q1 — 永続線形基底（XOR 区間最大値クエリ）

問題

制約