2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred) - C. Cloud Computing

概要

N日の間、K個の飴を毎日食べたい。近所の菓子屋にはM種類の飴があり、それぞれ[l_i, r_i]日の間に、毎日最大で1つあたりの値段p_i円でc_i個まで売っている。
あなたは、いい感じに購入して毎日K個の飴を食べたい。もしその日に売られてる飴がK個未満ならば、K個の飴を食べられないが、妥協して売られてる飴をすべて買って食べることとする。
N日間のうち、かかる費用の最小値を答えよ。

制約：　1 <= N, K, <= 10^6 1 <= M <= 2*10^5 1 <= l, r <= N, 1 <= c_i, p_i <= 10^6

ACするまで

1. データ構造っぽいなぁー。
2. 遅延セグ木に(値段, 個数)をモノイドとして乗っけてみようー＞ひたすらに同じ日の区間に飴の種類を追加されると険しい。
3. コンテストTLE

4. こういう時間軸を進めていくタイプの問題の解法としてありえるものとして、イベントソートがある。
5. ひとまず始まりの左端l_iと半開区間としてみなした右端r_i+1の時に、それぞれ飴が売られてる、売られてないように調整しておけば、その日その日売られてる飴のリストからいい感じに計算すればよい。
6. いい感じに計算するには、値段が安いものから順にk個とる必要がある。こういうのはBITを使って、[値段]=個数になるようにして左端からの和がちょうどkを超えた場所を見つければよい。
7. これは、BITの上を二分探索するテクに該当する。これをやることでAC! (実行時間的にはギリギリなので、BIT上二分探索をしないとおそらく落ちる)

考察

このように、日にちごとに使用可能なリソースが変動する場合、[l, r]の日にちの間に使用可能というのを、[l, r+1)の半開区間に使用可能とみなして、

l日目の時にリソースを使用可能の一覧に追加する。
r+1日目の時にリソースを使用可能の一覧から消去する。

そしてこの追加と消去を終えた時、使用可能一覧からその日その日の計算をする。

このテクニックをイベントソートとAtcoder解説で呼ばれたのでこうとしよう。

今回の場合、これで考えると問題は「使用可能の一覧からコストが安い方からK個とるときのコストの最小をO(log N)くらいで求める」になる。

これは、「いくつかの(個数, 価格)中から小さい方をK個とる」という典型問題で、ものの追加と求値、そして二分探索すべてO(log N)でできるセグメント木やBITで解くことができる。
[価格]=個数　となるようにBITを構築して、前からK個を超えるになるのはいくつの価格か？をBIT上の二分探索でできる。
そして計算の便宜上[価格]=その商品の個数*価格　となる別のBITを用意して、計算する際に二分探索してわかった価格までこれを合計しておけば、K個を超えた分を引いておくことでその日のかかる値段の最小値が分かる。

BITの二分探索の資料：
http://hos.ac/slides/20140319_bit.pdf

ACソースコード：
Submission #67062912 - Codeforces