Day 116-Q2 | 3次元Mo's Algorithm

問題

長さ$N$の数列$A$に対し、$Q$個のクエリをオフラインで処理せよ。クエリは次の2種類である。

1 l r — 区間$[l,r]$（1-indexed、両端含む）に含まれる相異なる値の個数を出力する。このクエリより前に行われたすべての更新を反映した状態に対して答える
2 p x — 位置$p$の値を$x$に変更する

入力形式

N
A_1 A_2 ... A_N
Q
query_1
query_2
...
query_Q

制約

$1 \le N, Q \le 2000$

$1 \le A_i, x \le N$

入出力例

入力例1

出力例1

初期状態$[1,2,1,3,2]$の全体の相異なる値は$\{1,2,3\}$で$3$。2 3 5で$[1,2,5,3,2]$になり$4$。2 1 5で$[5,2,5,3,2]$になり全体は$3$、区間$[3,5]$の$[5,3,2]$も$3$。

概念図: (l, r, t) の3軸ソートと尺取りの移動

ヒント（段階的開示）

ヒント1: 方向性

更新がない区間クエリだけなら、Mo's algorithmで$(l,r)$を$\sqrt{N}$分割してソートし、尺取り法で$O((N+Q)\sqrt{N})$で解ける。しかし今回は点更新が混ざっている。クエリのたびに配列をコピーして最新状態を再構築すると計算量が悪化してしまう。更新の「時刻」もMo's algorithmの分割軸に加えることを考える。

ヒント2: アプローチ

各クエリを$(l,r,t)$の3つ組とみなす。$t$は「そのクエリの直前までに行われた更新の回数」を表す。クエリを$(l/\text{block}, r/\text{block}, t)$の順でソートしてオフライン処理し、$l,r$をMo's algorithmのように尺取り的に動かすのに加えて、$t$も尺取り的に前後に動かす。$t$を進めるときはその更新を「適用」し、戻すときは「取り消し（revert）」する。更新対象の位置が現在の区間$[cur\_l,cur\_r]$の中に入っているかどうかで、相異なる値のカウントを更新するかどうかが変わる点に注意する。

ヒント3: 誘導（コード骨格）

queries.sort(key=lambda q: (q.l // block, q.r // block, q.t))
cur_l, cur_r, cur_t = 0, -1, 0
for l, r, t in queries:
    while cur_r < r: cur_r += 1; add(cur_r)
    while cur_l > l: cur_l -= 1; add(cur_l)
    while cur_r > r: remove(cur_r); cur_r -= 1
    while cur_l < l: remove(cur_l); cur_l += 1
    while cur_t < t: apply_update(cur_t); cur_t += 1
    while cur_t > t: cur_t -= 1; revert_update(cur_t)
    ans[qi] = distinct

模範解答 (Python)

import sys
from collections import defaultdict


def solve():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    A = [int(data[idx + i]) for i in range(N)]; idx += N
    Q = int(data[idx]); idx += 1

    state = A[:]      # 全更新を反映した「最終的な」配列（更新を記録するために使う）
    updates = []       # (pos, old, new) 更新の履歴（時系列順、0-indexed pos）
    queries = []        # (l, r, t, qi) 0-indexed l, r / t = その時点までの更新回数

    for _ in range(Q):
        typ = data[idx]; idx += 1
        if typ == '1':
            l = int(data[idx]) - 1
            r = int(data[idx + 1]) - 1
            idx += 2
            queries.append((l, r, len(updates), len(queries)))
        else:
            p = int(data[idx]) - 1
            x = int(data[idx + 1])
            idx += 2
            old = state[p]
            updates.append((p, old, x))
            state[p] = x

    block = max(1, round(N ** (2 / 3))) if N > 0 else 1

    def sort_key(q):
        l, r, t, qi = q
        lb = l // block
        rb = r // block
        return (lb, rb if lb % 2 == 0 else -rb, t)

    queries.sort(key=sort_key)

    cur_state = A[:]   # Moの尺取りが今見ている「時刻cur_t」時点での配列
    freq = defaultdict(int)
    distinct = 0

    def add(pos):
        nonlocal distinct
        v = cur_state[pos]
        if freq[v] == 0:
            distinct += 1
        freq[v] += 1

    def remove(pos):
        nonlocal distinct
        v = cur_state[pos]
        freq[v] -= 1
        if freq[v] == 0:
            distinct -= 1

    cur_l, cur_r, cur_t = 0, -1, 0

    def apply_update(t):
        p, old, new = updates[t]
        if cur_l <= p <= cur_r:
            remove(p)
        cur_state[p] = new
        if cur_l <= p <= cur_r:
            add(p)

    def revert_update(t):
        p, old, new = updates[t]
        if cur_l <= p <= cur_r:
            remove(p)
        cur_state[p] = old
        if cur_l <= p <= cur_r:
            add(p)

    ans = [0] * len(queries)
    for l, r, t, qi in queries:
        while cur_r < r:
            cur_r += 1
            add(cur_r)
        while cur_l > l:
            cur_l -= 1
            add(cur_l)
        while cur_r > r:
            remove(cur_r)
            cur_r -= 1
        while cur_l < l:
            remove(cur_l)
            cur_l += 1
        while cur_t < t:
            apply_update(cur_t)
            cur_t += 1
        while cur_t > t:
            cur_t -= 1
            revert_update(cur_t)
        ans[qi] = distinct

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


solve()

計算量: $l,r,t$ の移動距離の総和がバランスするようブロックサイズを$N^{2/3}$に取ることで全体$O(N^{5/3})$（更新回数もクエリ数も$N$と同オーダーの前提）。ランダムクエリ500ケースで、区間ごとの愚直集計と全出力が一致することを確認済み。

Step-by-Step 解説

1クエリを$(l,r,t)$の3つ組として捉える
通常のMo's algorithmは$(l,r)$の2次元、今回は「更新の適用回数$t$」という3つ目の軸が加わる。3次元Mo's algorithmと呼ばれる所以。

2ソート順とブロックサイズ
$(l/\text{block}, r/\text{block}, t)$の順でソートする。理論上最適なブロックサイズは$N^{2/3}$になる（$l,r$の移動距離と$t$の移動距離のバランスを取った結果）。

3apply_update / revert_update の対称性
更新対象の位置$p$が現在の探索区間$[cur\_l,cur\_r]$の中にあるかどうかで、freqとdistinctを更新するかどうかが変わる。書き換える「前」に区間内ならremove、書き換えた「後」に区間内ならadd。

4add/removeによるdistinctカウントの維持
標準的なMo's algorithmの尺取りと同じく、頻度が0から1になったらdistinctを増やし、1から0になったら減らす。

5手計算によるトレース確認
入力例1を手計算すると、更新の前後でdistinctが正しく変化することを追える。実装後は必ず小さい例で手計算と突き合わせる。

よくあるミス

ミス	原因	正しい書き方
クエリのたびに配列を全部再構築して集計し直し、計算量が$O(NQ)$に劣化する	3次元目（時刻）を尺取りの対象にする発想に至らない	クエリを$(l,r,t)$の3つ組とみなし、$t$も尺取り的に前後に動かす
`apply_update`/`revert_update`で「更新位置$p$がウィンドウ内にあるか」の判定を怠り`freq`/`distinct`がずれる	配列の値を書き換えるだけで集計の更新を忘れる	値変更の前後どちらのタイミングで`remove`/`add`するかを明確に分けて実装する
ブロックサイズを$N$だけで決め、更新回数の影響を考慮しない	3次元Moの最適ブロックサイズが$N^{2/3}$であることを知らない	$\text{block} \approx N^{2/3}$（更新回数もNのオーダーと仮定）に設定する
`revert_update`で古い値ではなく新しい値を書き戻してしまう	apply/revertの対称性を誤解する	`revert_update`は`cur_state[p]`を`old`に戻す処理であることを明記して実装する

次のステップ

発展: クエリごとの集約関数を「相異なる値の個数」以外（区間和・区間XOR・最頻値など）に一般化してみる
発展: 3次元Moを「クエリに応じて任意の過去バージョンを見る」形に拡張し、永続データ構造（今回のQ3）との使い分けを比較する

自己評価

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

Day 116-Q2 — 3次元Mo's Algorithm（時間軸付きオフライン区間クエリ・点更新対応の区間内相異なる値の個数）

問題