Day 045-Q4 | 区間Mexクエリ（Mo's + SegTree）

問題

長さ $N$ の非負整数列 $a_1, \dots, a_N$ と $Q$ 個のクエリが与えられる。各クエリ l r に対して、$a_l, a_{l+1}, \dots, a_r$ に含まれない最小の非負整数（Mex）を求めよ。

制約

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

$0 \le a_i \le N$

$1 \le l_i \le r_i \le N$

時間制限: 3秒

$O((N+Q)\sqrt{N} \log N)$ を目標

入出力例

入力例 1

7 4
0 1 2 0 1 3 4
1 3
2 5
1 7
3 6

出力例 1

概念図: Mo's Algorithm + Mex管理セグメント木

ヒント（段階的開示）

ヒント1: 方向性

区間Mexクエリを全て個別に解くと $O(NQ)$。Mo's Algorithmで区間を効率的に管理し、Mex値を高速に求めるセグメント木と組み合わせる。

ヒント2: アプローチ

Mo's Algorithmで区間 $[l, r]$ を管理 $O((N+Q)\sqrt{N})$
セグメント木で「cnt[v]==0 の最小値」を管理
add/remove は $O(\log N)$、get_mex は $O(1)$（根を読むだけ）

ヒント3: 実装骨格

# セグ木: cnt[v]==0 の最小v を管理
tree[SIZE + v] = v  # 初期: 全値がMex候補
def update(v, delta):
    cnt[v] += delta
    pos = SIZE + v
    tree[pos] = v if cnt[v]==0 else MAXV
    pos >>= 1
    while pos >= 1:
        tree[pos] = min(tree[2*pos], tree[2*pos+1])
        pos >>= 1
get_mex = lambda: tree[1]

# Mo's
queries.sort(key=lambda q: (q[0]//B, q[1] if (q[0]//B)%2==0 else -q[1]))
cl, cr = 0, -1
for l, r, qi in queries:
    while cr < r: cr+=1; update(a[cr], 1)
    while cl > l: cl-=1; update(a[cl], 1)
    while cr > r: update(a[cr], -1); cr-=1
    while cl < l: update(a[cl], -1); cl+=1
    ans[qi] = get_mex()

模範解答 (Python)

import sys
from math import isqrt

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

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

    B = max(1, isqrt(N))
    queries.sort(key=lambda q: (q[0] // B, q[1] if (q[0] // B) % 2 == 0 else -q[1]))

    MAXV = N + 2
    SIZE = 1
    while SIZE < MAXV:
        SIZE <<= 1

    tree = [MAXV] * (2 * SIZE)
    for i in range(MAXV):
        tree[SIZE + i] = i
    for i in range(SIZE - 1, 0, -1):
        tree[i] = min(tree[2*i], tree[2*i+1])

    cnt = [0] * MAXV

    def update(v, delta):
        if v >= MAXV:
            return
        cnt[v] += delta
        pos = SIZE + v
        tree[pos] = v if cnt[v] == 0 else MAXV
        pos >>= 1
        while pos >= 1:
            tree[pos] = min(tree[2*pos], tree[2*pos+1])
            pos >>= 1

    def get_mex():
        return tree[1]

    ans = [0] * Q
    cl, cr = 0, -1

    for l, r, qi in queries:
        while cr < r:
            cr += 1
            update(a[cr], 1)
        while cl > l:
            cl -= 1
            update(a[cl], 1)
        while cr > r:
            update(a[cr], -1)
            cr -= 1
        while cl < l:
            update(a[cl], -1)
            cl += 1
        ans[qi] = get_mex()

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

main()

Step-by-Step 解説

1Mo's Algorithm の基本
クエリを「ブロック番号順（偶数↑、奇数↓zig-zag）」にソートすることで、区間の移動総量を $O((N+Q)\sqrt{N})$ に抑える。

2Mex管理のセグメント木
各値 $v$ のカウント $cnt[v]$ を管理し、「$cnt[v] == 0$ の最小 $v$」を高速取得するセグ木を使う。葉ノード: $cnt[v]=0$ なら値 $v$、$cnt[v]>0$ なら $MAXV$。内部ノード: 子の最小値。

3add/remove: $O(\log N)$
$cnt[v]$ を更新し、0←→1 の変化時のみセグ木の葉を更新 → 根まで更新伝播。

4get_mex: $O(1)$
セグ木の根 tree[1] が常に「現在の区間でcnt=0の最小値」= Mex。

5$a_i > N$ の扱い
長さ $N$ の配列の Mex は高々 $N$ なので、$a_i > N$ の値は Mex に影響しない。if v >= MAXV: return でスキップ。

計算量

Mo's 移動量: $O((N+Q)\sqrt{N})$
各 add/remove: $O(\log N)$
get_mex: $O(1)$
全体: $O((N+Q)\sqrt{N} \log N)$
空間: $O(N)$

よくあるミス

ミス	原因	正しい書き方
Mo's のzig-zag最適化を忘れる	最適化なしだと遅い	偶数ブロック↑、奇数ブロック↓
セグ木サイズが MAXV 未満	Mex=N+1 が返せない	`MAXV = N + 2` で設定
a[i] >= MAXV を処理してしまう	配列外参照	`if v >= MAXV: return` でガード
クエリの答えを qi に格納しない	Mo's ソート後の順序が変わる	`ans[qi] = get_mex()`

次のステップ

発展問題: 区間Mexクエリに点更新も加えた「動的Mexクエリ」を $O(N \log^2 N)$ で解く
類題: Mo's Algorithm on Trees（木上のMo法）との統合
応用: Mex を応用した競技数学問題（Sprague-Grundy 値の計算）

自己評価

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