ABC 401-500/ABC459C - Drop Blocks - 競技プログラミング用 知識集積所

---

問題

ABC459C

必要知識

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

• 特になし

考え方

愚直にやると、クエリ1でもクエリ2でも全マスチェックすることになり、TLEする。
そこで高速化を考える。

まず、クエリ2の高速化。
各マスに何個ブロックがあるかだけでなく、指定個数以上のブロックがあるマスがいくつあるかもデータとして用意する。
後者は最高で1マスにQ個ブロックが置かれるので、長さを少なくともQ+1で用意する。（「少なくとも」である理由は注意点を参照）

そして、例えば、2番のマスに3個目が置かれたときには、

• 2番目のマスの個数を2から3にする
• 3個以上あるマスの個数を1増やす

の2つの処理をするようにすればよい。
そうすれば、2番のクエリは後者のデータのうちの1要素を見るだけで答えられる。
クエリ2はこれで高速化完了。

次はクエリ1だが、これは実は自動的に解決している。
というのは、全マスに1個以上あるかの確認は、指定個数以上のブロックがあるマスがいくつあるかのデータを見ればすぐにわかる。
そして実際に削除する作業だが、実は削除作業の回数が追加作業の回数を超えることは絶対にないので、全クエリ通してO(Q)であり、TLEのリスクはない。

よって、これで両クエリ高速化できたので、あとは気を付けて実装するだけである。

解答例

解答例

注意点

おバカなクエリが飛んでくる

競プロには（少なくともAtCoderには）珍しいことだが、クエリ2におバカな数値が飛んでくる。
3つしかクエリがない（ブロックが全体で最大3個しかない）のに、「300000個以上ブロックがあるマス数は？」など。
指定個数以上のブロックがあるマスがいくつあるかを入れるvectorは、Q+1個あればクエリ1の処理時に困ることはないが、それだとクエリ2で範囲外アクセスでエラーする場合がある。
クエリ数にかかわらず300001以上の長さを用意するか、Qより大きい場合は別処理で0を答えるかすること。

別解

削除部分も高速化する。

削除時に実際にデータを1ずつ減らすのではなく、「1個ずつ消えたことになっている」というデータを持つ。
そして、クエリ2のときにyの値を調整することで削除も高速化できる。
ただ、そもそもブロック積みよりも軽い上に、ただでさえバグりやすいクエリ2の処理が複雑化するので、実はハイリスクローリターンなだけである。
解答例