ABC478Dを解いた【イベントソート】

筆者はレート800前後の茶～緑コーダ

ABC478のD問題を解いていく

実装コード

各クエリを区間の開始・終了イベントに分けてソートし、左から順に見ながら各位置を覆っている x の種類数を出力する。

• クエリ l, r, x を0-indexedに直し、(l, x, 1) と (r, x, -1) の2つのイベントとして queue に追加する
• 最後の位置まで出力しきるために、番兵として (N, 0, 0) も追加する
• queue をソートして、位置の小さい順にイベントを処理する
• cnt[x] は今の位置を覆っている x の区間の個数、ans は cnt[x] が1以上の x の種類数を表す
• イベントの位置 t まで now を進めながら、その間の位置の答えとして ans を出力する
• cnt[x] が 0 から増えるなら ans を1増やし、更新後に 0 になったら ans を1減らす
• 番兵(v == 0)は出力を進めるだけで何も更新しない

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    N, Q = rLI()
    queue = []
    for _ in range(Q):
        l, r, x = rLI()
        l -= 1
        x -= 1
        queue.append((l, x, 1))
        queue.append((r, x, -1))
    queue.append((N, 0, 0))
    queue.sort()

    cnt = [0] * Q
    ans = 0
    now = 0
    for t, x, v in queue:
        while now != t:
            now += 1
            print(ans, end=' ')
        if v == 0:
            continue
        if cnt[x] == 0:
            ans += 1
        cnt[x] += v
        if cnt[x] == 0:
            ans -= 1
    print()

if __name__ == '__main__':
    main()

感想

区間の開始と終了をイベントに分けてソートし、左から順に処理する考え方がポイントだと思った。
番兵を入れておくと最後の位置までまとめて出力できるのも便利だった。