コンテンツにスキップ

ABC478 D - Range Set Insertion Query

サイト
AtCoder
コンテスト
ABC478
問題
D - Range Set Insertion Query
難易度
729

はじめ空の集合 S1,…,SNS_1, \ldots, S_N に対して、「SL,…,SRS_L, \ldots, S_R に値 XX を追加する」という操作を QQ 回行います。最後に各 SiS_i の要素数を求める問題です(N,Q≤2×105N, Q \le 2 \times 10^5)。

SiS_i の要素数は「ii を含む区間が 1 つ以上ある値 XX の個数」です。同じ XX の区間が重なっていると、単純にいもす法で数えたときに XX を 2 回以上数えてしまうのが問題です。

そこで、値 XX ごとに区間をまとめ、重なっている区間を併合して互いに重ならない区間の集まりにしてから、いもす法で +1+1 します。こうすれば、各位置で同じ XX が数えられるのは高々 1 回です。

区間の併合は、区間を左端でソートして前から見ていき、今の区間の左端が直前にまとめた区間の右端以下なら右端を伸ばし、そうでなければ新しい区間として追加すればできます。

XX でソートしてから同じ XX ごとに処理し、計算量はソートの O(Qlog⁡Q)O(Q \log Q) といもす法の O(N)O(N) を合わせて O(N+Qlog⁡Q)O(N + Q \log Q) です。

コードでは区間を半開区間 [L−1,R)[L - 1, R) で持っているので、隣り合っているだけの区間(右端 == 次の左端)も併合されますが、和集合は変わらないので問題ありません。

Python
from operator import itemgetter
N, Q = map(int, input().split())
LRX = [tuple(map(int, input().split())) for i in range(Q)]
LRX.sort(key=itemgetter(2))
imos = [0] * (N + 1)
i = 0
while i < Q:
x = LRX[i][2]
tmp = [(LRX[i][0] - 1, LRX[i][1])]
i += 1
while i < Q and LRX[i][2] == x:
tmp.append((LRX[i][0] - 1, LRX[i][1]))
i += 1
tmp.sort()
l = []
for a, b in tmp:
if l and l[-1][1] >= a:
l[-1] = (l[-1][0], max(l[-1][1], b))
else:
l.append((a, b))
for a, b in l:
imos[a] += 1
imos[b] -= 1
for i in range(N):
imos[i + 1] += imos[i]
print(*imos[:N])