Day 070-Q3 | Mo's with Updates（動的区間存在クエリ + 乱択・確率的解析）

問題

$N$ 個の整数 $a_1, \ldots, a_N$ からなる配列と $Q$ 個のクエリが与えられる。クエリの前に $P$ 個の点更新 U i v（$a_i \leftarrow v$）が任意順で到着する。各クエリ QQ l r k は、更新が適用済みの状態で区間 $[l, r]$ に値 $k$ が存在するかを答える。

制約

パラメータ	範囲
$N$	$1 \le N \le 5 \times 10^5$
$P$	$0 \le P \le 10^5$
$Q$	$1 \le Q \le 5 \times 10^5$
$a_i, v, k$	$1 \le a_i, v, k \le 10^9$
$l, r$	$1 \le l \le r \le N$

入出力例

入力例 1

出力例 1

YES
YES
NO

更新後の配列: [3,1,2,1,5]。Q1: a[1..3]={3,1,2} に 2 あり YES。Q2: a[2..5]={1,2,1,5} に 1 あり YES。Q3: a[1..5] に 6 なし NO。

概念図: Mo's with Updates の3次元ソート

ヒント（段階的開示）

ヒント1: 方向性

Mo's with Updates はクエリを $(l/B, r/B, t)$ の3次元でソートし、ブロックサイズ $B = N^{2/3}$ とすることで更新を含む区間クエリを $O((N+Q) \cdot N^{2/3})$ で処理する。

ヒント2: アプローチ

クエリを $(l, r, t)$ の3次元でソート
現在の $(cur\_l, cur\_r, cur\_t)$ をクエリの $(l, r, t)$ に近づける
$t$ を調整: 更新を適用・取り消し（区間内外で cnt を更新するかどうかが変わる）
$l, r$ を拡張・縮小
cnt[k] > 0 なら YES

ヒント3: コード骨格

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

cur_l, cur_r, cur_t = 0, -1, 0
cnt = defaultdict(int)

def apply_upd(t, reverse=False):
    pos, old_v, new_v = updates[t]
    if not reverse:
        if cur_l <= pos <= cur_r:
            cnt[cur_a[pos]] -= 1
            cur_a[pos] = new_v
            cnt[new_v] += 1
        else:
            cur_a[pos] = new_v
    else:
        if cur_l <= pos <= cur_r:
            cnt[cur_a[pos]] -= 1
            cur_a[pos] = old_v
            cnt[old_v] += 1
        else:
            cur_a[pos] = old_v

模範解答 (Python)

import sys
from collections import defaultdict

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    P = int(data[idx]); idx += 1
    Q_cnt = int(data[idx]); idx += 1

    a = [int(data[idx + i]) for i in range(N)]
    idx += N

    updates = []
    queries = []
    cur_a = a[:]

    for _ in range(P + Q_cnt):
        op = data[idx].decode(); idx += 1
        if op == 'U':
            i = int(data[idx]) - 1; idx += 1
            v = int(data[idx]); idx += 1
            updates.append((i, cur_a[i], v))
            cur_a[i] = v
        else:
            l = int(data[idx]) - 1; idx += 1
            r = int(data[idx]) - 1; idx += 1
            k = int(data[idx]); idx += 1
            queries.append((l, r, len(updates), k, len(queries)))

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

    cur_a = a[:]
    cnt = defaultdict(int)
    cur_l, cur_r, cur_t = 0, -1, 0

    def add(pos):
        cnt[cur_a[pos]] += 1

    def remove(pos):
        cnt[cur_a[pos]] -= 1

    def apply_upd(t, reverse=False):
        pos, old_v, new_v = updates[t]
        if not reverse:
            if cur_l <= pos <= cur_r:
                cnt[cur_a[pos]] -= 1
                cur_a[pos] = new_v
                cnt[new_v] += 1
            else:
                cur_a[pos] = new_v
        else:
            if cur_l <= pos <= cur_r:
                cnt[cur_a[pos]] -= 1
                cur_a[pos] = old_v
                cnt[old_v] += 1
            else:
                cur_a[pos] = old_v

    answers = [''] * len(queries)

    for l, r, t, k, qid in queries:
        while cur_t < t:
            apply_upd(cur_t); cur_t += 1
        while cur_t > t:
            cur_t -= 1; apply_upd(cur_t, reverse=True)
        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
        answers[qid] = "YES" if cnt[k] > 0 else "NO"

    sys.stdout.write('\n'.join(answers) + '\n')

solve()

Step-by-Step 解説

Step 1: Mo's Algorithm の基本

区間クエリをオフラインで処理する手法。クエリを $(l/B, r)$ でソートし $l, r$ ポインタの移動量を $O((N+Q)\sqrt{N})$ に抑える。

Step 2: Mo's with Updates の拡張

更新を含む場合、クエリを $(l/B, r/B, t)$ の3次元でソートし $B = N^{2/3}$ にする。更新の適用・取り消しを追加で管理する。

Step 3: 更新の適用と取り消し

更新対象インデックスが現在の区間 $[cur\_l, cur\_r]$ 内か外かで cnt の更新が変わる。区間内なら古い値の cnt を -1、新しい値の cnt を +1。

Step 4: クエリの答え

cnt[k] > 0 なら区間内に $k$ が存在。

Step 5: 計算量分析

操作	計算量
$l, r$ の移動	$O(Q \cdot B + N \cdot N/B)$
$t$ の移動	$O(Q \cdot P/B^2 \cdot B)$
最適 $B = N^{2/3}$	全体 $O((N+Q) \cdot N^{2/3})$

よくあるミス

ミス	原因	正しい書き方
区間内外で cnt 更新を区別しない	区間外更新で cnt を変えると不整合	`if cur_l <= pos <= cur_r` でガード
ブロックサイズが $\sqrt{N}$ のまま	更新なしの Mo's と混同	更新ありなら $B = N^{2/3}$
取り消し時に new_v と old_v を逆転	reverse フラグの処理ミス	`reverse=True` で old_v に戻す
Python では TLE	定数係数が大きい	PyPy3 推奨 or C++ 実装

次のステップ

発展問題: Mo's Algorithm + XOR 線形基底（区間 XOR 最大値 + 追加クエリ）
Rollback Mo（削除不可データ構造）との比較
ブロック分解オンラインクエリとの比較
並列二分探索との組み合わせ

Day 070-Q3 — Mo's with Updates（動的区間存在クエリ + 乱択・確率的解析）

問題

制約