二次元いもす法 矩形区間加算処理O(1)、矩形区間総和取得処理O(1)、更新処理O(HW) #include <bits/stdc++.h> namespace NyaaLIB { /** * 二次元いもす法 * 矩形区間加算処理O(1)、矩形区間総和取得処理O(1)、更新処理O(HW) **/ template <class T = int64_t> struct DS_NyaaImos2D { int64_t ys</class></bits/stdc++.h>…

boost using bit=boost::dynamic_bitset<>; using mi=boost::multiprecision::cpp_int; using mf=boost::multiprecision::cpp_dec_float_100; 定数 const char en='\n'; const long long inf=2000000000000000000; const long long maxll=922337203685477580…

概要 https://imoz.jp/algorithms/imos_method.html 累積和の機能を持つので累積和の上位互換として使える。 単純な累積和だと値の更新はできないが、いもす法なら任意のタイミングで値の更新が出来る。 メンバ関数 コンストラクタ lib_imos(ll sz); lib_imo…

graph 深さ優先探索 dfs https://9871225.hatenablog.com/entry/2021/11/25/232020 幅優先探索 bfs https://9871225.hatenablog.com/entry/2025/10/19/071614 ダイクストラ法（単一始点最短経路） auto dijkstra 単一始点から全ての終点までの最短経路を求め…

https://atcoder.jp/contests/agc018/submissions/23809861 最大の状態から減らすには何を減らせばよいか考える 最大の状態から始めて小さくするには「最大の要素を取り除くしかない」という貪欲 数字を変化させるには「少なくとも貪欲するしかない」なら貪…

https://atcoder.jp/contests/zone2021/submissions/23283470 辺の張り方とコストが特殊なとき、辺の数を減らして同値な移動を再現可能 コストを増やしたい→階層化して辺を追加すれば再現可能 上下左右1マス移動しかないなら単純にダイクストラ法をするだけ…

https://atcoder.jp/contests/abc203/submissions/23082310 小さい数を-1、大きい数を+1、としてカウントすると線形処理で中央値かどうか判別可能 中央値を求めるデータ構造として2個の priority_queue を持つ のアルゴリズムがあり、スライドウィンドウして…