ABC260E - At Least One

考え方

区間$[l, r]$を考える（$1 \leq l \leq r \leq M$）．

$l$を固定し，$r$を良い数列になるまで動かす．このとき，$r^{\prime} \geq r$に対し，区間$[l, r^{\prime}]$に対応する数列はすべて良い数列なので，個数をカウントする．

上を$l=1,...,M$に対して実施する．

---

「$r$を良い数列になるまで動かす」方法を考える．

• $l=1$のとき，$r = \max_{i}(A_{i})$となるまで動かせば良い．
• $l=A_{i} + 1$に動かしたとき，$r \geq B_{i}$となるまで動かせば良い（条件を満たす$i$が複数存在しうることに注意）．
• $l=\min(B_{i}) + 1$に動かしたとき，$r$をどのように動かしても．良い数列は得られない．

回答例

from collections import defaultdict

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

maxA = max(a for a, _ in AB)
minB = min(b for _, b in AB)
setA = set(a for a, _ in AB)
invA = defaultdict(list)
for i, (a, b) in enumerate(AB):
    invA[a].append(i)

cnt = [0] * (M + 2)
l, r = 1, maxA
while l <= minB:
    cnt[r - l + 1] += 1
    cnt[M - l + 1 + 1] -= 1
    if l in setA:
        r = max(r, max(AB[i][1] for i in invA[l]))
    l += 1
for i in range(len(cnt) - 1):
    cnt[i + 1] += cnt[i]

print(*cnt[1:M + 1])