Edit

【pythonでABC194を解説】E - Mex Min

問題概要

問題ページ

E - Mex Min
E - Mex Min

問題ページへ移動する

問題文

\(\mathrm{mex}(x_1, x_2, x_3, \dots, x_k)\) を、\(x_1, x_2, x_3, \dots, x_k\) に含まれない最小の非負整数と定義します。
長さ \(N\) の整数列 \(A = (A_1, A_2, A_3, \dots, A_N)\) が与えられます。
\(0 \le i \le N - M\) を満たす全ての整数 \(i\) について \(\mathrm{mex}(A_{i + 1}, A_{i + 2}, A_{i + 3}, \dots, A_{i + M})\) を計算したとき、この \(N - M + 1\) 個の値のうちの最小値を求めてください。

制約

  • \(1 \le M \le N \le 1.5 \times 10^6\)
  • \(0 \le A_i \lt N\)
  • 入力に含まれる値は全て整数

問題の考察

ACコード

import sys


class SegmentTree:
    def __init__(self, size, f=lambda x, y: min(x, y), default=10 ** 15):
        self.size = 2 ** (size - 1).bit_length()
        self.default = default
        self.dat = [default] * (self.size * 2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1])

    def query(self, left, right):
        left += self.size
        right += self.size
        left_res, right_res = self.default, self.default
        while left < right:
            if left & 1:
                left_res = self.f(left_res, self.dat[left])
                left += 1

            if right & 1:
                right -= 1
                right_res = self.f(self.dat[right], right_res)
            left >>= 1
            right >>= 1
        res = self.f(left_res, right_res)
        return res


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    df = 10 ** 7
    n, m = list(map(int, input().rstrip('\n').split()))
    st = SegmentTree(n + 1)
    for i in range(n + 1):
        st.update(i, i)
    a = list(map(int, input().rstrip('\n').split()))
    ls = [i for i in range(n + 1)]
    for i in range(m):
        st.update(a[i], ls[a[i]] + df)
        ls[a[i]] += df
    ans = [st.query(0, n + 1)]
    for i in range(m, n):
        st.update(a[i-m], ls[a[i-m]] - df)
        ls[a[i-m]] -= df
        st.update(a[i], ls[a[i]] + df)
        ls[a[i]] += df
        ans.append(st.query(0, n + 1))
    print(min(ans))


if __name__ == '__main__':
    solve()

-Edit
-