Day 040-Q2 | 平方分割 + 区間相異なる値カウント

問題

長さ $N$ の整数列 $A$ に対し $Q$ クエリを処理せよ。

クエリ1: 1 l r x — $A[l..r]$ 全要素に $x$ を加算
クエリ2: 2 l r — $A[l..r]$ 内の相異なる値の個数を出力

制約

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

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

$|A_i|, |x| \le 10^9$

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

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

入出力例

入力例 1

6 4
3 1 4 1 5 9
2 1 6
1 2 4 2
2 1 6
2 3 5

出力例 1

5
5
2

概念図: 平方分割の構造

ヒント（段階的開示）

ヒント1: 方向性

平方分割（$\sqrt{N}$ ブロック）で各ブロックにソート済み配列 + lazy オフセット + 生データを管理。加算クエリは完全ブロックに lazy を加算するだけ、端数は直接変更後に再ソート。

ヒント2: distinct カウント

lazy は全要素に同じ値を加算するため、distinct 個数は変化しない。端数ブロックは set に追加、完全ブロックはソート済み配列を走査して distinct を set に追加（offset 付き）。

ヒント3: 実装骨格

BLOCK = 450
# ブロック b の実値 = raw[b][i] + lazy[b]
# 更新（完全ブロック）: lazy[b] += x
# 更新（端数）: raw[b][i] += x; blocks[b] = sorted(raw[b])
# distinct クエリ: vals = set()
#   端数: vals.add(raw[bl][i] + lazy[bl])
#   完全: vals.update(v + lazy[b] for v in distinct_sorted(blocks[b]))

模範解答 (Python)

import sys
from collections import defaultdict
input = sys.stdin.readline

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

    BLOCK = 450
    blocks = []
    lazy = []
    raw = []

    b = 0
    while b < N:
        chunk = A[b:b+BLOCK]
        raw.append(list(chunk))
        blocks.append(sorted(chunk))
        lazy.append(0)
        b += BLOCK

    def get_block(i): return i // BLOCK
    def block_start(b): return b * BLOCK
    def block_end(b): return min((b+1)*BLOCK, N)

    def update_range(l, r, x):
        bl, br = get_block(l), get_block(r)
        if bl == br:
            for i in range(l, r+1):
                raw[bl][i - block_start(bl)] += x
            blocks[bl] = sorted(raw[bl])
        else:
            for i in range(l, block_end(bl)):
                raw[bl][i - block_start(bl)] += x
            blocks[bl] = sorted(raw[bl])
            for b in range(bl+1, br):
                lazy[b] += x
            for i in range(block_start(br), r+1):
                raw[br][i - block_start(br)] += x
            blocks[br] = sorted(raw[br])

    def query_range(l, r):
        bl, br = get_block(l), get_block(r)
        vals = set()
        if bl == br:
            for i in range(l, r+1):
                vals.add(raw[bl][i - block_start(bl)] + lazy[bl])
        else:
            for i in range(l, block_end(bl)):
                vals.add(raw[bl][i - block_start(bl)] + lazy[bl])
            for b in range(bl+1, br):
                off = lazy[b]
                prev = None
                for v in blocks[b]:
                    if v != prev:
                        vals.add(v + off)
                        prev = v
            for i in range(block_start(br), r+1):
                vals.add(raw[br][i - block_start(br)] + lazy[br])
        return len(vals)

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

solve()

Step-by-Step 解説

1平方分割の設計
配列を $\sqrt{N} \approx 450$ サイズのブロックに分割。各ブロックはソート済み配列（distinct カウント用）と生データ配列（部分更新用）+ lazy オフセットを管理。

2加算クエリ
完全ブロックは lazy に x を加算するだけ（O(1) per block）。端数ブロックは生データを直接更新 → 再ソート（O(B log B)）。

3Distinct カウントクエリ
端数ブロックは生データから set に追加。完全ブロックはソート済み配列を走査し distinct 値を set に追加（lazy オフセット付き）。最終的に set の要素数が答え。

4lazy とdistinct の関係
lazy は全要素に同じ値を加算するため、ブロック内の distinct 個数は変化しない。ただしクエリをまたぐ場合は異なるブロックの値が重複する可能性があるため set で管理。

5計算量
更新: $O(\sqrt{N} \log \sqrt{N})$ per query。カウント: $O(N)$ worst。全体: $O(Q\sqrt{N})$。

計算量

ブロック数: $O(\sqrt{N})$
更新クエリ: $O(\sqrt{N} \log \sqrt{N})$ per query
カウントクエリ: $O(N / \sqrt{N} \cdot \sqrt{N}) = O(N)$ worst case
全体: $O(Q\sqrt{N})$

よくあるミス

ミス	原因	正しい書き方
lazy を distinct カウントに適用忘れ	offset 加算を忘れる	`vals.add(v + off)`
端数ブロックに lazy を適用したまま	部分更新後に lazy がずれる	部分更新時は raw を直接変更して lazy は触れない
再ソートを忘れる	raw 更新後にブロックを再構築	`blocks[bl] = sorted(raw[bl])`
1-indexed/0-indexed ミス	`l-1, r-1` で 0-indexed に変換	入力時に変換統一

次のステップ

発展: オフライン Mo's Algorithm でクエリ2のみを $O(N\sqrt{Q})$ で処理
応用: 動的な distinct カウントには Segment Tree + 座標圧縮 + 遅延伝播
類題: 区間 AND/OR クエリ + 相異なるビットパターン数え上げ

自己評価

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