競技プログラミングにおけるimos法・累積和問題まとめ

累積和・imos法

• 累積和
  • 累積の和をとっておくと、区間の総和がO(1)で取得できる 参考
  • 累積和は、先頭からの和だけでなく、先頭からの積・先頭からのgcdも可能である。交換則も必要ないので、行列に対しての計算も可能である
  • 【テク1】ある要素以外の最大とかを求めたいときは、先頭からと後尾からの累積和を取る典型がある
  • 2次元に拡張することもできる
• imos法
  • 一定区間にある数を足すクエリを仕込みO(1),後処理O(N)で行う方法 本家解説
  • 普通は0次1次元であるが、高次高次元に拡張できる(らしい)
  • なんかすごい記事が爆誕してた

問題

• 累積和
  • 1次元累積和
    • yukicoder No.607 開通777年記念 （累積和とlower_boundの典型問題（尺取り法がより良い解法））解法
    • ABC084 2017-like Number 解説（クエリを累積和で高速に処理する基本）
    • 【テク1】ABC134C Exception Handling 解説
    • HR Maximum Palindromes 解説
    • CF463 Recursive Queries 解説
    • AC 巨大チェスボード 解説
    • CF Rectangles 解説
    • AC Abundant Resources 解説
    • ABC122 GeT AC 解説
    • ABC125 GCD on Blackboard 解説
  • 2次元累積和
    • CSAcademy Rectangle Path
    • JOI休憩スペース (Refreshment Area)
    • ARC089 Checker 解説
    • CSA74 Two Squares
    • ARC097 Sorted and Sorted 解説
  • 特殊な累積和
    • yukicoder No.655 E869120 and Good Triangles 解説

• imos法
  • 0次1次元imos法(一般的なimos法)
    • ABC035 オセロ 解説
    • AOJ 予約システム
    • AOJ 大崎
    • CF179 Greg and Array 解説
  • CSA61 Paint the Fence 解説
    • CF376 80-th Level Archeology 解説
    • ABC080 Recording 解説
  • 0次2次元imos法(2次元imos法)
    • yukicoder No.60 魔法少女
    • ECF27 Fire in the City
  • AC ハンコ 解説
  • 1次1次元imos法(2回imos法を回すらしい)
    • CF421 Mister B and PR Shifts
    • ARC077 guruguru
  • 2次1次元imos法（二次関数を実装する）
    • AOJ 対空シールド
  • より複雑なimos法
  • CSA68 Triangular Updates 解説
    • AC その味は甘くて 解説

• どっちもある
  • yukicoder No.755 Zero-Sum Rectangle 解説