二次元いもす法 矩形区間加算処理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>…

ll btest(ll x, ll i); 整数xのi番目ビットが0か1か返す template <class T> void debug(T ... args); デバッグ出力 ll divc(ll x, ll y); 除算の天井関数 ceil(x / y) template void fillvv(T b, T e, S x); 二次元配列を値xで埋める template <class C> ll lcnt(C& c); c.cou</class></class>…

いもす法 区間加算 、区間総和取得 、更新処理 https://imoz.jp/algorithms/imos_method.html 累積和の機能を追加することで累積和の上位互換としても使える。 単純な累積和だと値の更新はできないが、このライブラリは任意のタイミングで値の更新も可能。 #…

GRAPH 深さ優先探索 auto dfs https://9871225.hatenablog.com/entry/2021/11/25/232020 ダイクストラ法（単一始点最短経路） auto dijkstra LIB::Dijkstra 単一始点から全ての終点までの最短経路を求める https://9871225.hatenablog.com/entry/2022/05/22/…

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 を持つ のアルゴリズムがあり、スライドウィンドウして…