August Long Challenge 2017: Hill Jumping
正答数を見る限りだと正攻法ではないんだろなとは思う。
- 計算量
- \(O(100 Q \log N)\)
- キーワード
- link-cut tree | envelope
考察
- 各点におけるジャンプ先を
succ[i]
とする。変更クエリにより書き換わるsuccの要素数はたかだか200である。 - succ[i]で繋いでいくと木になる。この問題は木上のkth-ancestorを求める問題と見做せる。
- link-cut treeによりlink, cut, kth-ancestorはいずれも
O(log N) amortized
で処理できる。 - kth-ancestorは二分探索木のkth-minと同様
#include <iostream> #include <algorithm> #include <vector> #include <string> #include <deque> #include <cassert> using namespace std; constexpr int N = 1e5 + 10; struct node { node *l = nullptr; node *r = nullptr; node *p = nullptr; int size = 1; int key; }; bool is_root(node *x) { return !x->p || (x != x->p->l && x != x->p->r); } int size(node *x) { return x ? x->size : 0; } void fix(node *x) { x->size = 1 + size(x->l) + size(x->r); } void rot(node *x) { node *y = x->p; node *z = y->p; if (z) { if (y == z->l) z->l = x; if (y == z->r) z->r = x; } x->p = z; y->p = x; if (x == y->l) { y->l = x->r; x->r = y; if (y->l) y->l->p = y; } else { y->r = x->l; x->l = y; if (y->r) y->r->p = y; } fix(y); } void splay(node *x) { while (!is_root(x)) { node *y = x->p; if (!is_root(y)) { node *z = y->p; rot((x == y->l) == (y == z->l) ? y : x); } rot(x); } fix(x); } void expose(node *x) { node *tmp = x; node *r = nullptr; while (x) { splay(x); x->r = r; fix(x); r = x; x = x->p; } splay(tmp); } void link(node *c, node *p) { expose(c); expose(p); p->r = c; c->p = p; fix(p); } void cut(node *x) { expose(x); x->l->p = nullptr; x->l = nullptr; fix(x); } int kth_element(node *x, int k) { expose(x); while (true) { if (size(x->r) == k) { break; } else if (k < size(x->r)) { x = x->r; } else { if (!x->l) { break; } k -= 1 + size(x->r); x = x->l; } } splay(x); return x->key; } long long ft[N]; void add(int k, int v) { for (k++; k < N; k += k & -k) { ft[k] += v; } } long long getval(int k) { long long ret = 0; for (k++; k > 0; k &= k - 1) { ret += ft[k]; } return ret; } int main() { int n, q; cin >> n >> q; for (int i = 0; i < n; i++) { int a; scanf("%d", &a); add(i, a); add(i + 1, -a); } vector<int> succ(n, -1); for (int i = 0; i < n; i++) { succ[i] = i; } vector<node *> nodes(n); for (int i = 0; i < n; i++) { nodes[i] = new node(); nodes[i]->key = i; } auto update = [&](int l, int r) { l = max(0, l); deque<int> mono; for (int i = min(n - 1, r + 100); i >= r + 1; i--) { while (!mono.empty() && getval(i) >= getval(mono.front())) { mono.pop_front(); } mono.push_front(i); } for (int i = r; i >= l; i--) { while (!mono.empty() && mono.back() > i + 100) { mono.pop_back(); } while (!mono.empty() && getval(i) >= getval(mono.front())) { mono.pop_front(); } mono.push_front(i); if (mono.size() == 1) { if (succ[i] != i) { cut(nodes[i]); } succ[i] = i; } else { if (succ[i] != i) { cut(nodes[i]); } succ[i] = mono[1]; link(nodes[i], nodes[mono[1]]); } } }; update(0, n - 1); while (q--) { int type; scanf("%d", &type); if (type == 1) { int u, cnt; scanf("%d %d", &u, &cnt); u--; printf("%d\n", kth_element(nodes[u], cnt) + 1); } else { int l, r, x; scanf("%d %d %d", &l, &r, &x); l--; r--; add(l, x); add(r + 1, -x); update(r - 99, r); update(l - 100, l - 1); } } }