結果
| 問題 | No.3466 Mex Ranges |
| コンテスト | |
| ユーザー |
 tyawanmusi
|
| 提出日時 | 2025-12-17 03:37:02 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
AC
|
| 実行時間 | 1,424 ms / 3,000 ms |
| コード長 | 10,811 bytes |
| 記録 | |
| コンパイル時間 | 279 ms |
| コンパイル使用メモリ | 78,404 KB |
| 実行使用メモリ | 155,688 KB |
| 最終ジャッジ日時 | 2026-02-28 13:02:11 |
| 合計ジャッジ時間 | 20,408 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 22 |
ソースコード
import sys
input = sys.stdin.buffer.readline
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():
# 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]) で更新される
n = int(input())
a = list(map(int, input().split()))
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()