「imos法を知らなかったので調べてみた」という記事です。
復習がてら…の方も宜しければどうぞご覧ください。
0.それはABC408を解いていた昨日のこと…
ABC408に遅れて参加した私は、灰色コーダーらしくC問題でつっかかって2完でした（紆余曲折を端折りましたがご容赦ください）。
https://atcoder.jp/contests/abc408/tasks/abc408_c
終わってから解法を見たり、Twitter（現：X）の反応を見ていると、みなさん口を揃えて「imos法 」のお話をされているわけです。
私は知らないぞimos法！というわけで調べてまとめました。実質備忘録です。
1.imos法について調べる
まずはさっくりとimos法とはどういうものかについてですが、アルゴリズム考案者いもす様のページより下記を引用させていただきます。
いもす法とは，累積和のアルゴリズムを多次元，多次数に拡張したものです．競技プログラミングでは 2 次元 1 次のものまでしか出題されませんが，2012 年の研究成果としてこれをより高次元の空間により高次数のいもす法を適用することにより信号処理分野・画像処理分野において利便性があることがわかっています．
つまり、累積和とは違う…？多次元的に拡張…？
というか正直私がぐだぐだいうよりページ見ていただくほうが早いことも確かですので、よろしければ下記リンクをどうぞ。
https://imoz.jp/algorithms/imos_method.html
また最初読解に時間がかかった（私には難しかった）こともありましたので、比較的初心者向けの下記記事も参考にさせていただきました。
https://note.com/kirimin_chan/n/n7663e3bb8a05
imos法、累積和の問題がまとめられているこちらも私が後で確認しようと思っております。
https://blog.hamayanhamayan.com/entry/2017/07/04/020117
2.累積和との違い
imos法の基本的な流れは以下の通りです。
- 配列の各区間の始点に加算、終点+1に減算を記録する
- 最後に累積和を取ることで、各要素の最終的な値を求める
上記を踏まえた上で、累積和は「配列の先頭から順に値を足し合わせていくこと」自体を指すアルゴリズムです。
一方、imos法は「区間に対する加算・減算」を効率的に処理するための手法、というふうに私は違いを認識しています。
imos法は、累積和の考え方を応用しており、「区間加算→累積和」という2段階で処理しているんだな、という捉え方です。
3.ABC408Cの実装
以上を踏まえて実装に入ります。言語はPythonです。
いずれはC++も書けるようになりたいものですね…。
実装例（Python）
N, M = map(int, input().split())
imos = [0] * (N + 1)
# 壁の区間加算を行う
for i in range(M):
L, R = map(int, input().split())
imos[L-1] += 1
imos[R] -= 1
# 壁の高さを累積和で出す
Walls = [imos[0]]
for i in range(1, N):
Walls.append(Walls[i-1]+imos[i])
# 一番薄い城壁が答え
print(min(Walls)
改めて実装すると、「区間加算→累積和」という流れがよく見えますね。
私の中ではこの感覚で今後解いていこうと思います。