Day 076-Q2 — Mo's Algorithm with Updates（更新付き Mo 法・区間異なる値の種類数 $O(Q^{5/3})$）

問題

長さ $N$ の数列 $A$ が与えられる。以下の $Q$ 個のクエリを処理せよ：

• クエリ P: P l r — 区間 $[l, r]$（1-indexed）に含まれる異なる値の種類数を出力する
• クエリ U: U i x — $A_i$ を $x$ に変更する

入出力例

6 4
1 2 3 1 2 3
P 1 6
U 2 4
P 1 6
P 2 5

3
4
3

初期: [1,2,3,1,2,3] → P(1,6): {1,2,3}=3種。U(2,4): [1,4,3,1,2,3]。P(1,6): {1,2,3,4}=4種。P(2,5): {4,3,1,2}=4種? → {1,2,3,4}のうち存在→3種(4,3,1,2)=4種。

概念図: 3 次元 Mo 法のソート

3次元Mo法では $(l//B,\; r//B,\; t)$ の順でクエリをソートする。ブロックサイズ $B = Q^{2/3}$ のとき全移動コストが $O(Q^{5/3})$ になる。

ヒント

B = max(1, int(len(point_queries) ** (2/3)))
indexed.sort(key=lambda x: (x[0]//B, x[1]//B, x[2]))

# 時刻を合わせる (前へ)
while ct < t:
    idx, old_v, new_v = updates[ct]
    if cl <= idx <= cr:
        remove(A_state[idx]); add(new_v)
    A_state[idx] = new_v
    ct += 1
# 時刻を合わせる (後へ)
while ct > t:
    ct -= 1
    idx, old_v, new_v = updates[ct]
    if cl <= idx <= cr:
        remove(A_state[idx]); add(old_v)
    A_state[idx] = old_v

模範解答

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    VMAX = 100001

    updates = []
    point_queries = []
    A_cur = A[:]

    for _ in range(Q):
        line = input().split()
        if line[0] == 'U':
            i, x = int(line[1]) - 1, int(line[2])
            updates.append((i, A_cur[i], x))
            A_cur[i] = x
        else:
            l, r = int(line[1]) - 1, int(line[2]) - 1
            point_queries.append((l, r, len(updates)))

    if not point_queries:
        return

    B = max(1, int(len(point_queries) ** (2/3)))
    indexed = [(l, r, t, qi) for qi, (l, r, t) in enumerate(point_queries)]
    indexed.sort(key=lambda x: (x[0]//B, x[1]//B, x[2]))

    A_state = A[:]
    cnt = [0] * VMAX
    distinct = 0

    def add(v):
        nonlocal distinct
        if cnt[v] == 0: distinct += 1
        cnt[v] += 1

    def remove(v):
        nonlocal distinct
        cnt[v] -= 1
        if cnt[v] == 0: distinct -= 1

    cl, cr, ct = 0, -1, 0
    answers = [0] * len(point_queries)

    for l, r, t, qi in indexed:
        while ct < t:
            idx, old_v, new_v = updates[ct]
            if cl <= idx <= cr:
                remove(A_state[idx]); add(new_v)
            A_state[idx] = new_v
            ct += 1
        while ct > t:
            ct -= 1
            idx, old_v, new_v = updates[ct]
            if cl <= idx <= cr:
                remove(A_state[idx]); add(old_v)
            A_state[idx] = old_v
        while cr < r:
            cr += 1; add(A_state[cr])
        while cl > l:
            cl -= 1; add(A_state[cl])
        while cr > r:
            remove(A_state[cr]); cr -= 1
        while cl < l:
            remove(A_state[cl]); cl += 1
        answers[qi] = distinct

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

main()

Step-by-Step 解説

Step 1: クエリの分類と時刻付け

更新クエリを updates リストに順番に記録する。各区間クエリには「直前の更新回数 $t$」を付与する。これが3次元目の軸になる。

Step 2: ブロックサイズ $B = Q^{2/3}$

通常の Mo 法では $B = \sqrt{N}$ が最適だが、時刻軸が加わると最適 $B$ が変わる。区間移動コスト $O(QB)$ と時刻移動コスト $O(QN/B)$ をバランスさせると $B = N^{1/2}$ ではなく $Q^{2/3}$ が最適。

Step 3: ソート順

$(l//B, r//B, t)$ の辞書順でソートする。これにより各軸の移動の合計が $O(Q^{5/3})$ に抑えられる。

Step 4: 時刻の前後移動

時刻を 1 進める: 更新インデックスが現在の区間 $[cl, cr]$ 内なら値を変更して add/remove。$A\_state$ も書き換える。時刻を 1 戻す: ct -= 1 してから old\_v に戻す（逆順）。

Step 5: 区間の伸縮と集計

通常の Mo 法と同様に $cl, cr$ を1ずつ伸縮し distinct（異なる値の種類数）を管理する。

よくあるミス

次のステップ

• 発展問題: 「更新付き区間 k 番目要素クエリ」→ Mo's with Updates + 二分探索（$O(Q^{5/3} \log N)$）

自己評価