ABC 401-500/ABC408C - Not All Covered - 競技プログラミング用 知識集積所

---

問題

ABC408C

必要知識

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

• 累積和
• 階差数列（未作成）

考え方

単純に守っている砲台の数が最も少ないところを探せばよい、ということはすぐにわかる。
そして、単純に城壁の数だけ配列を用意し、「l番目からr番目まで+1する」を砲台の数だけ繰り返せば終わるように見える。

しかし、砲台数も城壁数も最大で、しかも全砲台が全城壁を守っている場合、計算量が大変なことになる。
そのため、高速化をしなければならない。

vectorで連続範囲に同じ数を加える場合、階差数列（未作成）が使える。
l番目からr番目まで全部に+1する作業を、階差数列（未作成）のl番目を+1、r番目を-1して累積和を取る作業に変えられる。
範囲への加算が1回であればむしろ遅くなっているが、何度も一気に範囲加算する場合は累積和をまとめて1回取るだけで済むので高速化できる。

解答例

解答例

注意点

別解