接尾辞配列というのを使うと文字列検索でいろいろできるらしいので書いてみた 何も見ずに書くと蟻本のコードと比較したとき自分のコードがいかにぐちゃぐちゃか思い知らされる． #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int MA</vector></algorithm></cstring></cstdio>…

解説みて解いた．問題が木だったらとりあえずEuler-Tourを使えないか考えるとよさそう． 二次元にして長方形を塗るという考え方は頭がいい． #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int MAXN = 2010, MAXM = 500000; typedef pair<int,int> P; in</int,int></algorithm></vector></cstdio>…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2235 クエリを平方分割する問題．平方分割した後にいらない頂点をつぶすのが超大変． Union-Find treeでがんばってつぶす． 以前からあった辺が，今みている区間のなかで破壊されるとき，あらかじ…

分割統治っぽくなって，頂点数Nの部分木にたいしてO(f(n))の計算量がかかるとすると，全体の計算量はCentroid DecompositionをするとO(f(n) log n)になってはやい．追記：コードに誤りがあったので修正しました．まだあるかもしれない #include <cstdio> #include <vector> #</vector></cstdio>…