I: Shapes - CODE FESTIVAL 2014 決勝(オープン) | AtCoder
この問題は
- 平面走査をして木を作る
- LCA
の二つのフェーズに分かれています
平面走査
解説にはBITでごり押しすると書いてありますが、
平衡二分木ライブラリがあれば割とよくあるタイプの木になるので高速に書けます。20分くらいで書けました。
さすがに45度回転は自明。
平面走査すると、
[l, r]を追加
[l, r]を削除
[l, r]が与えられるから[a, b]でa<l, r<bとなるものの中で最もaが大きい物を取得
という3種類のクエリに答える問題になる
ただし全ての時間について全部のl, rはdinstinct
これはどのような平衡二分木で実現出来るだろうか
pair<int, int>(l, r)をソートしていれるsetを考える
setの頂点ごとに、部分木の要素のmax(r)を保持すればよい
[l, r]が与えられたとき、pair(l, r)でfindし、木をsplitする
そうすれば左側の木の要素[a, b]はすべてa<lを満たすし、右側はすべてl<aを満たす
なので、左側の木について、r<bを満たす最も右側の要素を取得すれば良い
コレについては、max(r)を保持しているのでそれを見ながら木を潜れば良い
LCA
LCAはムズカシイですね。しかもサンプルだけ通るバグを仕込んでしまって非常に辛かったです。
こういう2つ以上の問題がくっついている問題だと、バグを仕込んだときどちらを疑えばいいのか分からず非常に辛い
#include <iostream> #include <cstdio> #include <complex> #include <set> #include <vector> #include <stack> #include <tuple> #include <algorithm> #include <cassert> #include <cstring> using namespace std; typedef long long ll; typedef pair<int, int> P; typedef tuple<int, int, int> T; const int INF = 1<<29; struct Tree { using D = T; struct Node; using NP = Node*; static Node last_d; static NP last; struct Node { NP l, r; int sz; D v; int ma; Node(D v) :l(last), r(last), sz(1), v(v), ma(get<1>(v)) {} Node(NP l, NP r, int sz = 0) :l(l), r(r), sz(sz) {} void push() { } NP update() { sz = 1+l->sz+r->sz; ma = get<1>(v); if (l->sz) { ma = max(ma, l->ma); } if (r->sz) { ma = max(ma, r->ma); } return this; } int lb(D a) { if (!sz) return 0; if (a <= v) return l->lb(a); return l->sz + 1 + r->lb(a); } int ub(D a) { if (!sz) return 0; if (v <= a) return l->sz + 1 + r->ub(a); return l->ub(a); } int find(int x) { if (!sz) return -1; assert(ma != x); assert(x != get<1>(v)); if (!sz || ma < x) return -1; int res = r->find(x); if (res != -1) return res; if (x < get<1>(v)) return get<2>(v); return l->find(x); } } *n; static uint xor128(){ static uint x=123456789,y=362436069,z=521288629,w=88675123; uint t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } static NP merge(NP l, NP r) { if (!l->sz) return r; if (!r->sz) return l; l->push(); r->push(); if (xor128() % (l->sz + r->sz) < l->sz) { l->r = merge(l->r, r); return l->update(); } else { r->l = merge(l, r->l); return r->update(); } } static pair<NP, NP> split(NP x, int k) { if (!x->sz) return {last, last}; x->push(); if (k <= x->l->sz) { auto y = split(x->l, k); x->l = y.second; y.second = x->update(); return y; } else { auto y = split(x->r, k- x->l->sz -1); x->r = y.first; y.first = x->update(); return y; } } Tree() : n(last) {} Tree(NP n) : n(n) {} int sz() { return n->sz; } void merge(Tree r) { n = merge(n, r.n); } Tree split(int k) { auto u = split(n, k); n = u.first; return Tree(u.second); } void insert(D v) { auto u = split(n, lb(v)); n = merge(merge(u.first, new Node(v)), u.second); } void erase(D v) { assert(count(v)); auto u = split(n, lb(v)); n = merge(u.first, split(u.second, 1).second); } int count(D v) { return ub(v) - lb(v); } int lb(D v) { return n->lb(v); } int ub(D v) { return n->ub(v); } int find(int l) { Tree u = split(lb(T(l, -INF, 0))); int res = n->find(l); merge(u); return res; } }; Tree::Node Tree::last_d = Tree::Node(NULL, NULL, 0); Tree::NP Tree::last = &last_d; template<int V> struct LowestCommonAncestor { const static int LG = 25; int ro[LG][V]; int dps[V]; vector<int> g[V]; void add(int i, int j) { g[i].push_back(j); g[j].push_back(i); } void dfs(int p, int b) { assert(ro[0][p] == -1); ro[0][p] = b; dps[p] = (b == -1) ? 0 : dps[b]+1; for (int d: g[p]) { if (d == b) continue; dfs(d, p); } } void exec(int r) { memset(ro, -1, sizeof(ro)); dfs(r, -1); for (int i = 0; i < LG-1; i++) { for (int j = 0; j < V; j++) { ro[i+1][j] = (ro[i][j] == -1) ? -1 : ro[i][ro[i][j]]; } } } int query(int l, int r) { if (dps[l] < dps[r]) swap(l, r); int dd = dps[l]-dps[r]; for (int i = LG-1; i >= 0; i--) { if (dd < (1<<i)) continue; dd -= 1<<i; l = ro[i][l]; } if (l == r) return l; for (int i = LG-1; i >= 0; i--) { if (ro[i][l] == ro[i][r]) continue; l = ro[i][l]; r = ro[i][r]; } return ro[0][l]; } }; const int MN = 200200; typedef pair<int, T> E; vector<E> e; int query[MN][2]; LowestCommonAncestor<MN> lca; int main() { int n; cin >> n; n++; e.push_back(E(-INF, T(-INF, INF, n-1))); for (int i = 0; i < n-1; i++) { int x, y, r; cin >> x >> y >> r; e.push_back(E(y+x-r, T(y-x-r, y-x+r, i))); e.push_back(E(y+x+r, T(y-x-r, y-x+r, n+i))); } int m; cin >> m; for (int i = 0; i < m; i++) { int xa, xb, ya, yb; cin >> xa >> ya >> xb >> yb; e.push_back(E(xa+ya, T(ya-xa, ya-xa, 2*n+2*i))); e.push_back(E(xb+yb, T(yb-xb, yb-xb, 2*n+2*i+1))); } sort(e.begin(), e.end()); Tree t; for (E u: e) { int id = get<2>(u.second); if (id < n) { if (id != n-1) { lca.add(id, t.find(get<0>(u.second))); } t.insert(u.second); } else if (id < 2*n) { get<2>(u.second) -= n; t.erase(u.second); } else { query[(id-2*n)/2][id%2] = t.find(get<0>(u.second)); } } lca.exec(n-1); for (int i = 0; i < m; i++) { int l = query[i][0], r = query[i][1]; int ans = lca.query(l, r); cout << lca.dps[l] + lca.dps[r] - 2*lca.dps[ans] << endl; } return 0; }