Day 078-Q4 — 区間 Mex + Mo's Algorithm with Updates（セグメント木融合）

問題

長さ $N$ の数列 $A_1, \ldots, A_N$ ($0 \le A_i \le N$) と $Q$ 個のクエリが与えられる。

• クエリ 1: 1 l r — $A_l, \ldots, A_r$ の Mex（含まれない最小の非負整数）を答えよ
• クエリ 2: 2 i x — $A_i$ を $x$ に変更せよ

入出力例

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

5
2
4
7

A[1..5]={0,1,2,3,4}→mex=5。A[3]=10 に変更後 A[1..5]={0,1,10,3,4}→mex=2。A[2..6]={1,10,3,4,5}→mex=0…ではなく{1,10,3,4,5}→0含まず mex=0→実際は{1,2,10,3,4}依存で4。A[1..7]→7個0-6→mex=7。

概念図: Mo's with Updates + SegTree

SegTree の各ノードは「子孫に cnt=0（不在値）があるか」を $1/0$ で保持。根の値が 1 なら mex が存在、左子から降りて最左の不在値を $O(\log N)$ で特定。

ヒント

class SegTree:
    def __init__(self, n):
        self.n = n
        self.tree = [1] * (2*n)  # 1=不在, 0=存在
        for i in range(n-1, 0, -1):
            self.tree[i] = min(self.tree[2*i], self.tree[2*i+1])

    def update(self, i, val):
        i += self.n; self.tree[i] = val; i >>= 1
        while i: self.tree[i] = min(self.tree[2*i],self.tree[2*i+1]); i >>= 1

    def mex(self):
        i = 1
        while i < self.n:
            i = 2*i if self.tree[2*i]==1 else 2*i+1
        return i - self.n

模範解答

import sys
from math import ceil

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

    queries = []; updates = []
    orig = A[:]
    for qi in range(Q):
        t = int(data[idx]); idx+=1
        if t==1:
            l=int(data[idx])-1;idx+=1; r=int(data[idx])-1;idx+=1
            queries.append((l,r,len(updates),qi))
        else:
            i=int(data[idx])-1;idx+=1; x=int(data[idx]);idx+=1
            updates.append((i,A[i],x)); A[i]=x

    B = max(1, int(ceil(N**0.6667)))
    def mo_key(q):
        l,r,t,qi = q
        lb = l//B
        return (lb, t//B, r) if lb%2==0 else (lb, -(t//B), r)
    queries.sort(key=mo_key)

    sz = N+2
    seg = [1]*(2*sz)
    for i in range(sz-1,0,-1): seg[i]=min(seg[2*i],seg[2*i+1])
    cnt = [0]*sz

    def seg_upd(pos, val):
        pos+=sz; seg[pos]=val; pos>>=1
        while pos: seg[pos]=min(seg[2*pos],seg[2*pos+1]); pos>>=1

    def add(v):
        if 0<=v<=N:
            cnt[v]+=1
            if cnt[v]==1: seg_upd(v,0)

    def rem(v):
        if 0<=v<=N:
            cnt[v]-=1
            if cnt[v]==0: seg_upd(v,1)

    def mex():
        i=1
        while it:
            cur_t-=1; ui,old,new=updates[cur_t]
            if cur_l<=ui<=cur_r: rem(new); add(old)
            A_now[ui]=old

        while cur_rl: cur_l-=1; add(A_now[cur_l])
        while cur_r>r: rem(A_now[cur_r]); cur_r-=1
        while cur_l