ABC 401-500/ABC426F - Clearance - 競技プログラミング用 知識集積所

---

問題

ABC426F

必要知識

B以下レベルの内容は省略

• lazy segment木※

考え方

とりあえず、愚直解を考えてみる。

指定範囲の商品1つ1つについて、在庫の個数を確認し、変える個数を求め、実際に買う。
それを商品数だけループ、というのをクエリ数だけループ。
これで、O(NQ)でよければ解ける。

では、これのどこに高速化の余地があるかというと、すでに在庫切れした商品の扱いと、買い物をしたときの区間減算処理の2つ。

各商品に、在庫があるかどうかのフラグを用意する。
それをFenwick木※やsegment木※で管理すれば、区間内に在庫あり商品がいくつあるかは瞬時に求まる。
つまり、買う数を在庫あり商品数×kと見積もることができる。
そして、在庫が減るのはlazy_segment木※の区間加算を使えばよく、それなら一緒にフラグの個数もデータに載せることができる。

しかし、それだけでは問題がまだ2つ残る。
それは、中途半端に在庫があるが買いたい数に足りない場合の対応と、在庫切れの検出。

これらは、lazy_segment木※にさらに在庫数の最小値とその位置も載せることで対応できる。
全区間の最小値を探し、マイナスのものがあったら、それは注文した数だけ在庫がなかったということである。
よって、足りなかった数だけ購入数から引き算し、在庫ありフラグを折ればよい。
この際、在庫切れしたものの在庫数データはどうでもよいので、特大の値を入れてしまうことで最小値探索から除外する。

まとめると、

• 区間最小値とその位置および在庫が正であるフラグの個数を持ち、区間減算ができるlazy_segment木※を用意し、情報を入れておく
• クエリが来たら、とりあえず範囲内で在庫があるやつを全部k個買うことにしてしまう
• 最小値が負になっていたら、在庫不足だったということなので、購入数を調整し、在庫フラグを折り、在庫数を特大の値にする
  • 0の場合もまとめて在庫切れ扱いの処理をすると楽

区間減算は最大Q回、在庫切れ処理は最大N回なので、lazy_segment木※の処理にO(logN)くらいかかっても間に合う。

解答例

解答例

注意点

lazy segment木※の遅延データをlong long型にする

毎回の買う個数は10^9までだが、遅延データがいくつか重なってint型の範囲をはみ出る場合がある。
遅延データはlong long型で持つようにすること。

別解

別解というほどではないが、在庫があるかどうかのフラグは別途Fenwick木※などを用意してもよい。
そして、最小値の位置は、データに持たせなくても毎回二分探索※してもよい。
これらを両方やると、lazy segment木※に載せるデータが整数1つで済むので、人によっては楽になるかもしれない。