[ABC260E] At Least One を Pythonで解く

https://atcoder.jp/contests/abc260/tasks/abc260_e

考え方

A-B のペアが複数与えられ、全てのペアについて、少なくとも片方を含むような連続数列を求める問題です。部分数列を区間 $[L,R]$ と考え、尺取り法のように L,R を増やしていく操作を考えていきます。ある$[L,R]$ がA,Bのペアの少なくとも片方を含んでいるなら、Rを増やしていっても条件を満たします。

Lを1からスタートさせて、条件を満たすようなRの最小値を求めていきます。まず、L=1のときは、条件を満たすRの最小値は、Aの最大値になります。

{1,2,3} が条件を満たすなら、{1,2,3,4}、{1,2,3,4,5}、{1,2,3,4,5,6}、{1,2,3,4,5,6,7}、{1,2,3,4,5,6,7,8}、{1,2,3,4,5,6,7,8,9} も条件を満たすので、数列の長さは 3から9のものを1つずつカウントします。この部分は、いもす法を用いて数値変動を、長さ3のところで $+1$ とし、長さ10（いもす法では後ろの位置は1ずれることが多い）のところで $-1$ と記録しておき、最後に累積和を計算します。

Lを増やしたとき、あるペアの片方の数（A）がはみ出てしまったときには、もう片方を含むように、Rをずらします。

Lを増やしていきながら、この操作を繰り返すことを考えます。データとしては、Aの値それぞれに対して、ペアとなっているBの値を記録しておけば良いです。Aがはみ出たときには、Bの値を見てRをずらす位置が決まります（記録しておくのはBの最大値だけで良いです）。

実装メモ

N,M = map(int,input().split())
pair = [0]*(M+1)
imos = [0]*(M+2)
Amax = 0
Bmin = 10**10

for _ in range(N):
    a,b = map(int,input().split())
    pair[a] = max(pair[a],b)
    Amax = max(Amax,a)
    Bmin = min(Bmin,b)

LがBの最小値を超えると、条件を満たすことはできないので、forループは1からBの最小値の範囲でまわせば良いです。

r = Amax
for l in range(1,Bmin+1):
    imos[r-l+1] += 1
    imos[M-l+2] -= 1

    if pair[l] > 0:
        r = max(r,pair[l])

最後に累積和を計算する

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

print(*imos[1:M+1],sep=" ")