ABC478 D - Range Set Insertion Query

考え方

愚直にやるのは簡単だが、計算量が $O(NQ\log Q)$ でTLE。
そこで高速化を考える。

最終的にどんな値が入っているかは要求されない。
そこで、集合に数を挿入するのではなく、挿入範囲に $1$ 個増えたという情報をもたせればよさそう。
これは $X$ の値がすべて異なる場合には有効な方法。
階差数列に情報をまとめてから累積和を利用することで $O(N+Q)$ で済む。

ただし、実際には同じ $X$ の値が同じ集合に入れられる場合がある。
この場合、重複カウントをしないようにする必要がある。
そこで、集合への挿入順を変えてしまう。

操作順序を変えても最終結果は変わらない。
そこで、最初に $X$ の値ごとに操作を分類してしまう。
さらに同じ $X$ の中で $L$ の値が小さい順にソートして、区間重複分は $L$ や $R$ を削り落とせばよい。
そうすれば、同じ $X$ があっても、前述の方法で解決できる。
ソートが必要な分、計算量は $O(N+Q\log Q)$ になる。

入力例1での動作

入力を受け取る。

n: 8
q: 5

queries:
2 5 1
1 4 2
7 8 1
3 6 3
2 5 2

まず、操作を $X$ ごとに分類する。

X=1: [2,5], [7,8]
X=2: [1,4], [2,5]
X=3: [3,6]

同じ $X$ の区間について、重複する部分をまとめる。
$X=2$ の $[1,4]$ と $[2,5]$ は重複しているので、$[1,5]$ にまとめられる。

したがって、各 $X$ について残る区間は次のようになる。

X=1: [2,5], [7,8]
X=2: [1,5]
X=3: [3,6]

この各区間について、その範囲の集合の要素数が $1$ 増えるものとして階差数列に記録する。
$1$ から $9$ までの位置について変化量を並べると、次のようになる。

位置:   1  2  3  4  5  6  7  8  9
変化量: 1  1  1  0  0 -2  0  0 -1

これを左から累積和すると、位置 $1$ から位置 $8$ までの値は次のようになる。

1 2 3 3 3 1 1 1

したがって、答えは 1 2 3 3 3 1 1 1 である。

注意点

特になし。

別解

特になし。