…なければ解法は自明。永続multiset と永続配列があれば良い。永続multisetは使いまわせそうな形で再実装した。内部的には LLRBtree を用いている。 ポインタ型が64bitというのが厄介で、nodeにポインタ型を持たせるとMLEする。(CFは32bit環境らしい。なんでMLEしたんだ…？) #include <iostream> #include <algorithm> #include <vector> #include <map> #include <st…

…ことにしていたので、永続により空間O(Q log N)で保持できるということになる。 segtree上の[0,k)型クエリの二分探索は工夫することでO(log^2 n)からO(log N)に落とせる。fenwick tree上の二分探索(lower_bound)として有名？ 先読みソート+linked listを用いて動的更新に対応させた。 #include <iostream> #include <algorithm> #include <vector> #include …

…扱うテクニックとして永続的データ構造を用いるという方法がある。永続 segtree により解くことができるが、wavelet matrix を用いて解くこともできる。計算量は、構築O(n log x) 質問O(log x) である。 #include <iostream> #include <algorithm> #include <vector> using namespace std; // wavelet-matrix constexpr int N=75000*2; …

…c030_4 解法 永続平衡二分探索木を使えばいい。今回は LLRB を実装した。 LLRB というのは赤黒木に黒の右は赤ではないという条件（以下 LL 条件と呼ぶ）を加えたもの。対称性がないので反転機能をつけようと思うと困るのだが、割と簡単に実装できる。といっても普通の赤黒木でもjoin/splitは簡単な気がするが。 普通の赤黒木は以下のスライドを見ると良い。 https://www.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-d…

…らかにフェイクだが、永続を使っても普通に解ける。bitset を値とする永続配列を使えばいい。1024/64=16 なので 1 クエリあたりの負荷は軽い log と大差ない。こっちの方が本質的な処理がシンプルになるので楽。 Haskell でも通った。Haskell でビット並列を書く方法がわからないので Data.Set をノードに持たせた。ゴリゴリデータ構造を定義したが、デフォルトで永続配列ってあるのかな（Data.Map を使えばできるけど）。 よくあるデータ構造は大抵…

…i),x) である（このあたりが KMP に似ているのだろうか）。 p はただの配列で管理すればいいが、d は 1..106 までの値を持っているので愚直に持つのは厳しい。更新箇所が少ないので永続配列を使おう。 （よく考えたら KMP とか Aho-Corasick を使ってパターンマッチングオートマトンを作る作業と同じことをしてますね） EF は解説を読んで解いた。文字列系の問題は言われれば分かるんだけど、直感的理解みたいなのが中々得られない。慣れれば何とかなるんだろうか。

…これを可能にするのが永続 Union Find。 半永続（最新版しか更新できない）であれば更新時間の配列を使って簡単に実装できる。 本番中自分が投げたのは完全 16 分木の永続配列を用いた全永続（最新版以外の更新も可能）の Union-Find。計算量とメモリの効率が良くないのだが、直感的なのでこっちを使ってる。 コード中で i 番目までの UnionFind を ufs[i] に入れるというコードを書いている。 vector<UnionFind> ufs(m + 1); U…

…は難しい。 そこで"永続"平衡二分探索木を用いる。merge/split が使って次のような更新をすればいい。 dp' = dp[0..w[i]-1] ++ (dp[0..N-w[i]-1] + 1) merge/split の計算量は O(log n) だし、一様加算も遅延伝搬できるので問題ない。ところで 109 個頂点作った時点で MLE するのではと思うかもしれないが、永続を使えば陽に 109 個のノードを作る必要はない。次のような処理で 230 の木を作れる。 dp …

…セグメント木を作っておけばいい。 愚直に N 個セグメント木を作るのは難しい。こういうときは永続化してノードの大半を使い回せばいい。 gist.github.com wavelet matrix を使えば永続は不要。提出してないので AC するか分からないけど、手元のランダムケースでは異常がなかったので大丈夫かな。 （追記：2016/06/22) 通った。案の定(0,0)の処理を間違えていた。 gist.github.com 6完したが上手くない解き方ばかりしていた気がする。

…ling 以前書いた永続union-findが使いづらかったので永続配列で書きなおした。 問題 n 頂点 m 辺のグラフが与えられる。各頂点には T[i] という値が割り振られている。各辺には u[i] という値が割り振られている。 このとき、以下のクエリを Q 個処理せよ。 頂点 x と頂点 y を連結にし、かつ頂点 x の連結成分に属する distinct な T[i] の数が k 個以上になるように辺を選んでグラフを作る。このとき必要な辺のラベルの最小値を求める。 解法…

…いうことだろうか。 永続使えばできそう。 merge と revert を作ればいい。 これ永続必要ない…。 凸包を切ったり繋いだりするので、凸包は平衡二分探索木で表現するのが良さそう。 revert は凸包を切るだけなので、難しいのは merge。 凸包のマージには、凸多角形の共通接線を求めるアルゴリズムが必要。 点から凸多角形への接線は二分探索により O(log n)。 点から凸多角形への接線を反復適用することで、凸多角形の共通接線は定数×O(log n)？ 凸包は平衡二…

…,MLE が怖いけど永続で解けるのは明らかなので殴ったら通った。 辺コスト x 以下のグラフの set 付き unionfind が保持できればいい。もし保持できれば二分探索で答えを見つけることができる。 愚直に unionfind を保持すると O(n2) になるが、unionfind と set を永続化すれば多少現実的な計算量になる。set の永続化には RBST を使った。 座標圧縮しなくても動きはするが、二分探索のループ回数を減らすために座標圧縮は掛けた方がいい？二…

…要 D-Query 永続 + wavelet matrix。 計算量 O(n log2 n) 空間計算量 O(n log2 n) D-Query 永続とは？ 僕が勝手に名前をつけたテクニック。D-Query という問題の解法に由来する。 http://www.spoj.com/problems/DQUERY/ 問題は至ってシンプルで、A[l..r] に含まれる値の個数を unique に数えるというもの。 具体的な解法は Codeforces の以下のブログで説明されている。…

…る。 $$ dp[n][j]=dp[n][j-1]-dp[n/p[j-1]][j-1] $$ これを愚直に計算させると間に合わないが、n が小さいときは別の方法を取るようにすればギリギリ間に合う。 n が小さいときは区間総和セグメント木を永続化させたもので計算した。7986 ms。 Educational Codeforces Round 12 F. Four Divisors 本番ではまーすさんのライブラリをお借りして解いた。計算量がよくわからないけど間に合ってるので満足。