Day 092-Q4 — Mo's Algorithm（区間相異なる値の個数）

問題

長さ $N$ の数列 $a_1, \dots, a_N$ と $Q$ 個のクエリ l r が与えられる。各クエリで区間 $[l, r]$ に含まれる 相異なる値の個数 を出力せよ。

入出力例

6 3
1 2 1 3 2 3
1 3
2 5
1 6

2
3
3

$[1,3]=\{1,2\}$ で2種類。$[2,5]=\{2,1,3\}$ で3種類。$[1,6]=\{1,2,3\}$ で3種類。

概念図

ヒント

# cnt[値], 現在の種類数 cur を保持
# 追加: cnt[c]==0 → cur+=1 ; 削除: cnt[c]→0 → cur-=1
# 伸縮は「広げる → 縮める」の順で負のカウントを防ぐ

模範解答

import sys
import math

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); q = int(data[idx + 1]); idx += 2
    a = [int(data[idx + i]) for i in range(n)]; idx += n

    xs = sorted(set(a))
    comp = {v: i for i, v in enumerate(xs)}
    b = [comp[v] for v in a]

    queries = []
    for i in range(q):
        l = int(data[idx]) - 1; r = int(data[idx + 1]) - 1; idx += 2
        queries.append((l, r, i))

    block = max(1, int(n / max(1.0, math.sqrt(q))))

    def key(qr):
        l, r, i = qr
        blk = l // block
        return (blk, r if blk % 2 == 0 else -r)
    queries.sort(key=key)

    cnt = [0] * len(xs)
    ans = [0] * q
    cur = 0
    curL, curR = 0, -1

    for l, r, i in queries:
        while curR < r:               # 右を広げる
            curR += 1; c = b[curR]
            if cnt[c] == 0: cur += 1
            cnt[c] += 1
        while curL > l:               # 左を広げる
            curL -= 1; c = b[curL]
            if cnt[c] == 0: cur += 1
            cnt[c] += 1
        while curR > r:               # 右を縮める
            c = b[curR]; cnt[c] -= 1
            if cnt[c] == 0: cur -= 1
            curR -= 1
        while curL < l:               # 左を縮める
            c = b[curL]; cnt[c] -= 1
            if cnt[c] == 0: cur -= 1
            curL += 1
        ans[i] = cur

    sys.stdout.write('\n'.join(map(str, ans)) + '\n')

main()

計算量 $O((N+Q)\sqrt N)$。座標圧縮で cnt を配列にして高速化。

Step-by-Step 解説

Step 1: 座標圧縮

値は最大 $10^9$。cnt を配列で引くためランク $0..M-1$ に圧縮する。

Step 2: クエリのブロックソート

左端のブロックで一次ソート、同ブロック内は右端でソート。偶奇ブロックで昇順・降順を切り替える（ジグザグ）と右ポインタ総移動が減る。

Step 3: 伸縮の順序

「広げる（追加）を先、縮める（削除）を後」。逆順だと一時的に区間が破綻し cnt が負になり得る。

Step 4: 差分でカウント更新

追加で 0→1 は新種類、削除で 1→0 は種類消滅。cur を差分更新するだけで各ステップ $O(1)$。

よくあるミス

次のステップ

• 発展: 更新付き Mo（Mo with updates）で $O(Q^{5/3})$
• 発展: 区間内の異なる値の総和・mex クエリへ拡張
• 次回予告: Convex Hull Trick（分割コスト最小化DP）

自己評価