#1166580 (PyPy3) No.2930 Larger Mex

• 問題: No.2930 Larger Mex
• ユーザー: norioc
• 提出日時: 2026-05-25 04:21:50
• 言語: PyPy3 (7.3.17)
• 結果: AC
• 実行時間: 255 ms / 2,000 ms
• コード長: 5,180 bytes
• コンパイル時間: 2,502 ms
• コンパイル使用メモリ: 85,632 KB
• 実行使用メモリ: 127,104 KB
• 最終ジャッジ日時: 2026-05-25 04:22:10
• 合計ジャッジ時間: 12,766 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 50

ソースコード

import typing


def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1

    return x


class SegTree:
    def __init__(self,
                 op: typing.Callable[[typing.Any, typing.Any], typing.Any],
                 e: typing.Any,
                 v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = _ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)

        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        p += self._size
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)

    def get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

        return self._d[p + self._size]

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n
        sml = self._e
        smr = self._e
        left += self._size
        right += self._size

        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1

        return self._op(sml, smr)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    def max_right(self, left: int,
                  f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert f(self._e)

        if left == self._n:
            return self._n

        left += self._size
        sm = self._e

        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not f(self._op(sm, self._d[left])):
                while left < self._size:
                    left *= 2
                    if f(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1

        return self._n

    def min_left(self, right: int,
                 f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= right <= self._n
        assert f(self._e)

        if right == 0:
            return 0

        right += self._size
        sm = self._e

        first = True
        while first or (right & -right) != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not f(self._op(self._d[right], sm)):
                while right < self._size:
                    right = 2 * right + 1
                    if f(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)

        return 0

    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])


class Mex:
    def __init__(self, n: int):
        self.n = n
        self.freq = [0] * (n+1)
        self.inf = 1 << 60
        self.segt = SegTree(min, self.inf, list(range(n+1)))

    def add(self, x: int):
        assert x <= self.n
        self.freq[x] += 1
        if self.freq[x] == 1:
            self.segt.set(x, self.inf)

    def remove(self, x: int):
        assert x <= self.n and self.freq[x] > 0
        self.freq[x] -= 1
        if self.freq[x] == 0:
            self.segt.set(x, x)

    def get(self) -> int:
        """mex を返す"""
        return self.segt.all_prod()


from collections.abc import Callable


def shakutori(a: list, factory: Callable[[], 'WindowState']):
    n = len(a)
    state = factory()
    hi = -1
    for lo in range(n):
        if lo > hi:
            hi = lo - 1
            state = factory()

        # できるだけ伸ばす
        while hi+1 < n and state.can_expand(a[hi+1]):
            state.expand(a[hi+1])
            hi += 1

        if lo <= hi:
            yield state, lo, hi
            state.shrink(a[lo])  # lo をひとつ進める


class WindowState:
    def __init__(self):
        sz = 2 * 10**5 + 10
        self.mex = Mex(sz)
        pass

    def can_expand(self, x) -> bool:
        return self.mex.get() < M

    def expand(self, x):
        self.mex.add(x)

    def shrink(self, x):
        self.mex.remove(x)


N, M = map(int, input().split())
A = list(map(int, input().split()))

if M == 0:
    for i in reversed(range(1, N+1)):
        print(i)
    exit()


imos = [0] * (N+2)
for s, l, r in shakutori(A, WindowState):
    if s.mex.get() < M: continue

    w = r-l+1
    imos[w] += 1
    imos[N-l+1] -= 1

for i in range(1, N):
    imos[i+1] += imos[i]

ans = imos[1:N+1]
print(*ans, sep='\n')