解説みて解いた．問題が木だったらとりあえず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>…

StarrySkyを解こうとしました． 枝刈りしていないので半分ぐらいTLEします． #include <cstdio> #include <string.h> #include <algorithm> #define X first #define Y second using namespace std; const int MAXN = 4096; typedef pair<int, int> P; typedef pair<P, int> STAR; int N; int cx[MAXN], cy[M</p,></int,></algorithm></string.h></cstdio>…

問題 http://poj.org/problem?id=2019解法 segment tree の二次元版みたいなやつを作ると各クエリに対してO(log N)で処理できる #include <cstdio> #include <algorithm> using namespace std; typedef pair<int, int> P; const int N_ = 256; const int TREE_SIZE = 87381; // A_1 = 0, A</int,></algorithm></cstdio>…

問題解法 union-findを使う。 人数の2倍の大きさのUF木を作って、 「AとBが違う」を unite(a, b+N), unite(a + N, b) とする。 A,Bが同じ根を持つなら同じグループ、A,B+Nが同じ根を持つなら違うグループとなり どちらでもない場合は「まだ分からない」とな…

問題解法 Union-Find木を使って連結状態的なものを持っておく。 コンピュータpを修理したとき、他の修理されたコンピュータの中で距離d以内のものとuniteする 同じ根を持てば、通信可能である。 #include <cstdio> #include <algorithm> using namespace std; typedef pair<int, int> P; c</int,></algorithm></cstdio>…

問題 http://poj.org/problem?id=1990解法 x座標に関してBIT木を使っていろいろやる #include <cstdio> #include <algorithm> #define fst first #define snd second using namespace std; const int MAX_N = 20000; const int MAX_X = 20002; typedef pair<int,int> P; P cows[MAX_N]; i</int,int></algorithm></cstdio>…

問題 http://poj.org/problem?id=3264解法 SegmentTree で RMQ みたいなことをする。 自力でせぐつりーを実装できるようになった。 #include <cstdio> #include <algorithm> using namespace std; const int INF = 1 << 29; int n, a[100001 * 2], b[100001 * 2], q; // a:最大</algorithm></cstdio>…