Day 081-Q1 — クエリ平方分割（区間代入 × 区間 $k$ 番目・オンライン）

問題

長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ に対し，$Q$ 個のクエリをオンラインで処理せよ。

• update $l$ $r$ $v$: $A_l, \ldots, A_r$ を全て $v$ に更新（区間代入）
• query $l$ $r$ $k$: $A_l, \ldots, A_r$ の中から $k$ 番目に小さい値を答える

update と query は任意の順序で混在する。各 query の $l, r, k$ は直前の query の答えを XOR したオンライン形式で与えられる（最初の XOR 値 = 0）。

入出力例

7 6
3 1 4 1 5 9 2
U 2 5 7
Q 1 7 3
U 4 6 2
Q 3 7 2
U 1 3 5
Q 1 5 1

7
2
2

概念図: クエリ平方分割のブロック構造

ヒント

B = max(1, int(Q**0.5))  # ブロックサイズ
xor_acc = 0

for block_start in range(0, Q, B):
    block = queries[block_start:block_start + B]
    pending = []  # (l, r, v) のリスト

    for q in block:
        if q[0] == 'U':
            l, r, v = q[1], q[2], q[3]
            pending.append((l, r, v))
            for i in range(l, r+1): A[i] = v
        else:
            raw_l, raw_r, raw_k = q[1], q[2], q[3]
            l = (raw_l ^ xor_acc) - 1
            r = (raw_r ^ xor_acc) - 1
            k = raw_k ^ xor_acc
            seg = sorted(A[l:r+1])
            ans = seg[k-1]
            print(ans)
            xor_acc = ans

模範解答

import sys
input_data = sys.stdin.buffer.read().split()

def solve():
    idx = 0
    N = int(input_data[idx]); idx+=1
    Q = int(input_data[idx]); idx+=1
    A = [int(input_data[idx+i]) for i in range(N)]; idx+=N

    queries = []
    for _ in range(Q):
        t = input_data[idx].decode(); idx+=1
        if t == 'U':
            l, r, v = int(input_data[idx])-1, int(input_data[idx+1])-1, int(input_data[idx+2])
            idx+=3
            queries.append(('U', l, r, v))
        else:
            l, r, k = int(input_data[idx]), int(input_data[idx+1]), int(input_data[idx+2])
            idx+=3
            queries.append(('Q', l, r, k))

    B = max(1, int(Q**0.5))
    xor_acc = 0
    out = []

    i = 0
    while i < Q:
        block = queries[i:i+B]
        for q in block:
            if q[0] == 'U':
                l, r, v = q[1], q[2], q[3]
                for j in range(l, r+1):
                    A[j] = v
            else:
                raw_l, raw_r, raw_k = q[1], q[2], q[3]
                l = (raw_l ^ xor_acc) - 1
                r = (raw_r ^ xor_acc) - 1
                k = raw_k ^ xor_acc
                seg = sorted(A[l:r+1])
                ans = seg[k-1]
                out.append(ans)
                xor_acc = ans
        i += B

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

solve()

Step-by-Step 解説

Step 1: 問題の難しさを把握する

区間代入と区間 k 番目が混在する問題は標準的なデータ構造で対応困難：遅延セグメント木は k 番目に非対応，ウェーブレット木は更新が複雑。

Step 2: クエリ平方分割の基本方針

全クエリを $B \approx \sqrt{Q}$ のブロックに分割。各ブロック内の update を「即時 A に反映しながら」処理し，query 時は現時点の A を使う。

Step 3: オンライン復号

l = (raw_l ^ xor_acc) - 1  # XOR で復号 → 0-indexed
r = (raw_r ^ xor_acc) - 1
k = raw_k ^ xor_acc
xor_acc = ans  # 答えを次の XOR 値に

Step 4: 計算量の分析

単純版: $O(Q \cdot N \log N)$。真の平方分割最適化（pending を sorted list で管理してマージ）では $O(Q \sqrt{Q} \log Q)$ が達成できる。

よくあるミス

次のステップ

• 発展問題: 区間代入 + 区間積 k 番目（ウェーブレット木 + 遅延評価の統合）
• 参考: Chtholly Tree / ODT（区間代入特化 set ベース）

自己評価