要求される度に、uniqueやらeraseやら、1-indexやらの箇所で微妙に考えてしまうので、この際ライブラリ化しておく。 ※ 転倒数には、i < j でかつ、a_i > a_j であるとき転倒とする場合と、a_i >= a_j であるとき転倒とする場合の2種類があり、以下の実装は前…

他ライブラリ（転倒数等）で活用されることがあるので置いておく。 前提 Fenwick Treeとも 競プロにおいては、BITでできることは以下の2点であると抑えておこう。 累積和テーブルの更新: add 指定した区間の累積和の計算: sum 機能を限定することで扱いやす…

今まで文字列照合系問題は、DP(LCS)で頑張っていたけど、持っていたら便利そうだと思ったのでライブラリを用意してみた。 前提 Z-Algorithmとは、最長共通接頭辞の長さを線形時間で求めるアルゴリズム。 文字列の長さをnとして、O(n2)を、O(n)に改善できる …

クラスカル法など、他ライブラリから呼ばれることがあるので実装を置いておく。 前提 グループの管理を高速で行うことができるデータ構造 実態は木（森）になっている ある状態から、グループを併合することができ、分割することはできない UnionFind木の機…

前提 いずれも発想は貪欲法である。 クラスカル法 実装内容の理解についてはクラスカル法の方が楽 頂点数に対応する大きさのUnionFind木を用意する グラフの辺を、重みの小さい順に見ていき、(u, v)がまだ同じグループに属していないならばその辺を採用する…

前提 ダブリング手順 dp[i][j]:=頂点iの2j個上の頂点 iは頂点数nに対して、log_n 初期化: まずdpを-1で初期化したのち、dp[0][j]、つまり1個上のノードを登録する 以降、dp[i+1][j]=dp[i][dp[i][j]] で更新 ダブリングのわかりやすい解説 satanic0258.hatena…

セグメント木を抽象化したライブラリ(C++)を作成したのでまとめておく。 前提 セグメント木の実態は完全二分木 要素数nを扱いたいならn以上の2冪を葉の数とし、その数をwとすると、全体の要素数は2*w-1個となる 完全二分木において、要素i(>0)の親は(i-1)/2…