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

---

問題

ABC432E

必要知識

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

• Fenwick木※

考え方

クエリ2の中身がよくわからないが、場合分けしてみると

• l<r<Aならば、r
• l<A<rならば、A
• r<l<Aならば、l
• r<A<lならば、l
• A<l<rならば、l
• A<r<lならば、l
• 境界（2つ等しい場合）は、どちらを適用してもよい

ということになる。

もう少し整理すると、

• r<lならば、l（Aの値に関係ない）
• l<r<Aならば、r
• l<A<rならば、A
• A<l<rならば、l
• 境界（2つ等しい場合）は、どちらを適用してもよい

となる。

ということは、クエリ2でl>=rが与えられた場合、ただl*nを答えればいい。

問題はl<rのときで、この場合は、

• l未満であるAの個数 * l
• l以上r未満であるAの合計
• r以上であるAの個数 * r

を合計する必要がある。
これは、愚直にやると間に合わないが、実はAの上限が50万しかないのが鍵。

• 長さ50万1のFenwick木※で、指定区間の数の個数をすぐ出せるようにしておくと、1番目と3番目はすぐ出せる
• 長さ50万1のFenwick木※で、指定区間の数の合計をすぐ出せるようにしておくと、2番目はすぐ出せる

ということで、2本のFenwick木※を用いればクエリ2は間に合う。
あとは、クエリ1で、更新すべき場所を気を付けてもれなく更新するようにするだけである。

解答例

解答例

注意点

別解