結果
| 問題 | No.3466 Mex Ranges |
| コンテスト | |
| ユーザー |
 tyawanmusi
|
| 提出日時 | 2025-12-17 03:35:06 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
AC
|
| 実行時間 | 1,548 ms / 3,000 ms |
| コード長 | 15,672 bytes |
| 記録 | |
| コンパイル時間 | 397 ms |
| コンパイル使用メモリ | 82,224 KB |
| 実行使用メモリ | 166,788 KB |
| 最終ジャッジ日時 | 2026-02-28 13:01:51 |
| 合計ジャッジ時間 | 23,592 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge7 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 22 |
ソースコード
import sys
class InputError(Exception):
pass
class StrictIn:
def __init__(self, s: bytes, i: int = 0, line: int = 1, col: int = 1):
self.s = s
self.i = i
self.line = line
self.col = col
@staticmethod
def from_stdin_ascii() -> "StrictIn":
raw = sys.stdin.buffer.read()
for p, b in enumerate(raw):
if b >= 0x80:
raise InputError(f"non-ASCII byte at offset {p}: 0x{b:02x}")
if b in (0x09, 0x0A, 0x0D):
continue
if 0x20 <= b <= 0x7E:
continue
raise InputError(f"disallowed control byte at offset {p}: 0x{b:02x}")
return StrictIn(raw)
def _eof(self) -> bool:
return self.i >= len(self.s)
def _peek(self):
return None if self._eof() else self.s[self.i]
def _advance(self) -> int:
if self._eof():
self._err("unexpected EOF")
b = self.s[self.i]
self.i += 1
if b == 0x0A:
self.line += 1
self.col = 1
else:
self.col += 1
return b
def _err(self, msg: str) -> None:
raise InputError(f"{msg} (line {self.line}, col {self.col})")
def _consume_newline(self) -> None:
b = self._peek()
if b == 0x0A:
self._advance()
return
if b == 0x0D:
self._advance()
if self._peek() != 0x0A:
self._err("bare CR is not allowed (use LF or CRLF)")
self._advance()
self.line += 1
self.col = 1
return
self._err("expected EOL")
def skip_spaces(self) -> None:
while (not self._eof()) and (self._peek() in (0x20, 0x09)):
self._advance()
def skip_ws(self) -> None:
while not self._eof():
b = self._peek()
if b in (0x20, 0x09):
self._advance()
elif b in (0x0A, 0x0D):
self._consume_newline()
else:
break
def read_space(self) -> None:
b = self._peek()
if b not in (0x20, 0x09):
self._err("expected SPACE/TAB")
while (not self._eof()) and (self._peek() in (0x20, 0x09)):
self._advance()
def read_eoln(self) -> None:
self._consume_newline()
def read_eof(self) -> None:
if not self._eof():
self._err("expected EOF (extra data exists)")
def read_token(self) -> str:
b = self._peek()
if b is None:
self._err(f"unexpected EOF while reading token")
if b in (0x20, 0x09):
self._err(f"unexpected leading SPACE/TAB while reading token")
if b in (0x0A, 0x0D):
self._err(f"unexpected EOL while reading token")
start = self.i
while not self._eof():
b = self._peek()
if b in (0x20, 0x09, 0x0A, 0x0D):
break
self._advance()
return self.s[start:self.i].decode("ascii")
def read_int(self, lo=None, hi=None) -> int:
t_str = self.read_token()
t = t_str.encode("ascii")
if t[:1] == b"-":
body = t[1:]
if len(body) == 0:
self._err(f"int is not an integer")
else:
body = t
if len(body) == 0 or (not all(48 <= c <= 57 for c in body)):
self._err(f"int is not a base-10 integer")
x = int(t_str)
if lo is not None and x < lo:
self._err(f"int out of range: {x} < {lo}")
if hi is not None and x > hi:
self._err(f"int out of range: {x} > {hi}")
return x
def read_string(self, min_len: int | None = None, max_len: int | None = None) -> str:
s = self.read_token()
if min_len is not None and len(s) < min_len:
self._err(f"str too short: len={len(s)} < {min_len}")
if max_len is not None and len(s) > max_len:
self._err(f"str too long: len={len(s)} > {max_len}")
return s
class SegmentTreeBeats:
"""
SegmentTreeBeats
Initialization: SegmentTreeBeats(a)
Range Update:
update_add(l, r, x): a[i] += x for i in [l, r)
update_chmin(l, r, x): a[i] = min(a[i], x) for i in [l, r)
update_chmax(l, r, x): a[i] = max(a[i], x) for i in [l, r)
Range Query:
query_sum(l, r): sum(a[i] for i in [l, r))
query_min(l, r): min(a[i] for i in [l, r))
query_max(l, r): max(a[i] for i in [l, r))
"""
__slots__ = ["n0", "n", "h", "len", "sum", "max_v", "smax_v", "max_c", "min_v", "smin_v", "min_c", "add"]
INF = 10**30
def __init__(self, a):
n = len(a)
self.n0 = n
self.n = 1 << (n - 1).bit_length()
self.h = n.bit_length() - 1
size = 2 * self.n
self.len = [0] * size
self.sum = [0] * size
self.max_v = [-self.INF] * size
self.smax_v = [-self.INF] * size
self.max_c = [0] * size
self.min_v = [self.INF] * size
self.smin_v = [self.INF] * size
self.min_c = [0] * size
self.add = [0] * size
for i, v in enumerate(a):
k = self.n + i
self.len[k] = 1
self.sum[k] = v
self.max_v[k] = v
self.min_v[k] = v
self.max_c[k] = 1
self.min_c[k] = 1
for k in range(self.n - 1, 0, -1):
self._pull(k)
def _pull(self, k):
l = k << 1
r = l | 1
self.len[k] = self.len[l] + self.len[r]
self.sum[k] = self.sum[l] + self.sum[r]
if self.max_v[l] > self.max_v[r]:
self.max_v[k] = self.max_v[l]
self.max_c[k] = self.max_c[l]
self.smax_v[k] = max(self.smax_v[l], self.max_v[r])
elif self.max_v[l] < self.max_v[r]:
self.max_v[k] = self.max_v[r]
self.max_c[k] = self.max_c[r]
self.smax_v[k] = max(self.max_v[l], self.smax_v[r])
else:
self.max_v[k] = self.max_v[l]
self.max_c[k] = self.max_c[l] + self.max_c[r]
self.smax_v[k] = max(self.smax_v[l], self.smax_v[r])
if self.min_v[l] < self.min_v[r]:
self.min_v[k] = self.min_v[l]
self.min_c[k] = self.min_c[l]
self.smin_v[k] = min(self.smin_v[l], self.min_v[r])
elif self.min_v[l] > self.min_v[r]:
self.min_v[k] = self.min_v[r]
self.min_c[k] = self.min_c[r]
self.smin_v[k] = min(self.min_v[l], self.smin_v[r])
else:
self.min_v[k] = self.min_v[l]
self.min_c[k] = self.min_c[l] + self.min_c[r]
self.smin_v[k] = min(self.smin_v[l], self.smin_v[r])
def _apply_add(self, k, x):
if self.len[k] == 0:
return
self.sum[k] += x * self.len[k]
self.max_v[k] += x
self.min_v[k] += x
if self.smax_v[k] != -self.INF:
self.smax_v[k] += x
if self.smin_v[k] != self.INF:
self.smin_v[k] += x
self.add[k] += x
def _apply_chmin(self, k, x):
if self.len[k] == 0 or self.max_v[k] <= x:
return
self.sum[k] += (x - self.max_v[k]) * self.max_c[k]
if self.max_v[k] == self.min_v[k]:
self.max_v[k] = self.min_v[k] = x
elif self.max_v[k] == self.smin_v[k]:
self.max_v[k] = self.smin_v[k] = x
else:
self.max_v[k] = x
def _apply_chmax(self, k, x):
if self.len[k] == 0 or self.min_v[k] >= x:
return
self.sum[k] += (x - self.min_v[k]) * self.min_c[k]
if self.max_v[k] == self.min_v[k]:
self.max_v[k] = self.min_v[k] = x
elif self.min_v[k] == self.smax_v[k]:
self.min_v[k] = self.smax_v[k] = x
else:
self.min_v[k] = x
def _push(self, k):
if k >= self.n:
return
l = k << 1
r = l | 1
if self.add[k] != 0:
x = self.add[k]
self._apply_add(l, x)
self._apply_add(r, x)
self.add[k] = 0
pv_max = self.max_v[k]
pv_min = self.min_v[k]
if self.max_v[l] > pv_max:
self._apply_chmin(l, pv_max)
if self.max_v[r] > pv_max:
self._apply_chmin(r, pv_max)
if self.min_v[l] < pv_min:
self._apply_chmax(l, pv_min)
if self.min_v[r] < pv_min:
self._apply_chmax(r, pv_min)
def _push_to(self, k):
for s in range(self.h, 0, -1):
self._push(k >> s)
def _rebuild_from(self, k):
while k > 1:
k >>= 1
self._pull(k)
def update_add(self, l, r, x):
if l >= r:
return
assert 0 <= l < r <= self.n0
stack = [(1, 0, self.n, 0)]
while stack:
k, nl, nr, st = stack.pop()
if st == 1:
self._pull(k)
continue
if r <= nl or nr <= l or self.len[k] == 0:
continue
if l <= nl and nr <= r:
self._apply_add(k, x)
continue
self._push(k)
stack.append((k, nl, nr, 1))
m = (nl + nr) >> 1
stack.append(((k << 1) | 1, m, nr, 0))
stack.append((k << 1, nl, m, 0))
def update_chmin(self, l, r, x):
if l >= r:
return
assert 0 <= l < r <= self.n0
stack = [(1, 0, self.n, 0)]
while stack:
k, nl, nr, st = stack.pop()
if st == 1:
self._pull(k)
continue
if r <= nl or nr <= l or self.len[k] == 0 or self.max_v[k] <= x:
continue
if l <= nl and nr <= r and self.smax_v[k] < x:
self._apply_chmin(k, x)
continue
self._push(k)
stack.append((k, nl, nr, 1))
m = (nl + nr) >> 1
stack.append(((k << 1) | 1, m, nr, 0))
stack.append((k << 1, nl, m, 0))
def update_chmax(self, l, r, x):
if l >= r:
return
assert 0 <= l < r <= self.n0
stack = [(1, 0, self.n, 0)]
while stack:
k, nl, nr, st = stack.pop()
if st == 1:
self._pull(k)
continue
if r <= nl or nr <= l or self.len[k] == 0 or self.min_v[k] >= x:
continue
if l <= nl and nr <= r and self.smin_v[k] > x:
self._apply_chmax(k, x)
continue
self._push(k)
stack.append((k, nl, nr, 1))
m = (nl + nr) >> 1
stack.append(((k << 1) | 1, m, nr, 0))
stack.append((k << 1, nl, m, 0))
def query_sum(self, l, r):
if l >= r:
return 0
assert 0 <= l < r <= self.n0
res = 0
stack = [(1, 0, self.n)]
while stack:
k, nl, nr = stack.pop()
if r <= nl or nr <= l or self.len[k] == 0:
continue
if l <= nl and nr <= r:
res += self.sum[k]
continue
self._push(k)
m = (nl + nr) >> 1
stack.append(((k << 1) | 1, m, nr))
stack.append((k << 1, nl, m))
return res
def query_min(self, l, r):
if l >= r:
return self.INF
assert 0 <= l < r <= self.n0
res = self.INF
stack = [(1, 0, self.n)]
while stack:
k, nl, nr = stack.pop()
if r <= nl or nr <= l or self.len[k] == 0:
continue
if l <= nl and nr <= r:
v = self.min_v[k]
if v < res:
res = v
continue
self._push(k)
m = (nl + nr) >> 1
stack.append(((k << 1) | 1, m, nr))
stack.append((k << 1, nl, m))
return res
def query_max(self, l, r):
if l >= r:
return -self.INF
assert 0 <= l < r <= self.n0
res = -self.INF
stack = [(1, 0, self.n)]
while stack:
k, nl, nr = stack.pop()
if r <= nl or nr <= l or self.len[k] == 0:
continue
if l <= nl and nr <= r:
v = self.max_v[k]
if v > res:
res = v
continue
self._push(k)
m = (nl + nr) >> 1
stack.append(((k << 1) | 1, m, nr))
stack.append((k << 1, nl, m))
return res
def get(self, i):
assert 0 <= i < self.n0
k = 1
nl = 0
nr = self.n
while nr - nl > 1:
self._push(k)
m = (nl + nr) >> 1
if i < m:
k = k << 1
nr = m
else:
k = (k << 1) | 1
nl = m
return self.sum[k]
def set(self, i, v):
assert 0 <= i < self.n0
path = []
k = 1
nl = 0
nr = self.n
while nr - nl > 1:
path.append(k)
self._push(k)
m = (nl + nr) >> 1
if i < m:
k = k << 1
nr = m
else:
k = (k << 1) | 1
nl = m
self.len[k] = 1
self.sum[k] = v
self.max_v[k] = v
self.min_v[k] = v
self.smax_v[k] = -self.INF
self.smin_v[k] = self.INF
self.max_c[k] = 1
self.min_c[k] = 1
self.add[k] = 0
for k in reversed(path):
self._pull(k)
def solve_tle():
ins = StrictIn.from_stdin_ascii()
n = ins.read_int(lo=1, hi=200000)
ins.read_eoln()
a = []
for i in range(n):
v = ins.read_int(lo=0, hi=10**9)
if i != n - 1:
ins.read_space()
else:
ins.read_eoln()
a.append(v)
ins.read_eof()
ans = [0] * (n + 1)
for i in range(n):
mex_set = set()
for j in range(i, n):
mex_set.add(a[j])
mex = 0
while mex in mex_set:
mex += 1
ans[mex] += 1
for i in ans:
print(i)
def solve():
# dp[i][l] = (a_l, a_{l+1}, ..., a_r) に 0...i が全て含まれる最小の r, 存在しないなら n
# 区間の個数は sum(n - dp[i][l]) で求まる
# ans_i = sum(dp[i][l] - dp[i-1][l] for l in 0..n-1)
# i を増やしながら dp[i] を計算していく
# dp[i][l...idx[i]] = chmax(dp[i][l...idx[i]], idx[i]) で更新される
ins = StrictIn.from_stdin_ascii()
n = ins.read_int(lo=1, hi=200000)
ins.read_eoln()
a = []
for i in range(n):
v = ins.read_int(lo=0, hi=10**9)
if i != n - 1:
ins.read_space()
else:
ins.read_eoln()
a.append(v)
ins.read_eof()
idx = [[]for _ in range(n + 1)]
for i in range(n):
if a[i] > n:
continue
idx[a[i]].append(i)
ans = []
seg = SegmentTreeBeats(list(range(n)))
for i in range(n + 1):
prev = 0
for l in idx[i]:
seg.update_chmax(prev, l + 1, l)
prev = l + 1
seg.update_chmax(prev, n, n)
# sum(seg) = sum(dp[i])
# 区間の個数は始点を考える必要がある
# print([seg.get(j) for j in range(n)])
ans.append(seg.query_sum(0, n))
# print(ans)
# 全区間から区間の個数を引いている
print(n * (n + 1) // 2 - (n * n - ans[0]))
for i in range(n):
print(ans[i + 1] - ans[i])
if __name__ == "__main__":
solve()