P4175 [CTSC2008] 网络管理 Solution

Description

给定一棵 $n$ 个点的树 $T$，点有点权 $w_i$.
定义 $\mathrm{path}(u,v)$ 为 $u\to v$ 的路径上的点集.
执行 $q$ 次操作分两种：

• k u x（$k=0$）：令 $w_u\leftarrow x$.
• k u v（$k>0$）：设可重集 S={wi∣i∈path⁡(u,v)}S=\{w_i|i\in \operatorname{path}(u,v)\}S={wi​∣i∈path(u,v)}，求 $S$ 中第 $k$ 大的值，若 $k>|S|$ 输出 invalid request!.

Limitations

$1\le n,q\le 8\times 10^4$
$1\le u,v\le n$
$1\le w_i,x\le 10^8$
$0\le k\le n$
$2\text{s},500\text{MB}$

Solution

题目不强制在线，可以把询问全部离线下来.
看到求第 $k$ 大，可以用整体二分，具体见 P2617.
不过这题是树上操作，所以分治中用的 BIT 要改成单点加，链和查询，套个树剖就好了.

由于树剖每次查询会剖出 $O(\log n)$ 个区间，整体二分本身的复杂度为 $O(n{\log }^{2}n)$，故时间复杂度为 $O(n{\log }^{3}n)$，不过常数很小，可以在 $200\text{ms}$ 内跑完.

Code

$5.2\text{KB},1.39\text{s},26.61\text{MB}\text{(c++20 with o2)}$
代码是用两份拼接的，不会有人想看吧 .

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}struct Node {int tp, val;int le, ri;int pos;Node(int _tp = 0, int _val = 0, int _le = 0, int _ri = 0, int _pos = 0):tp(_tp), val(_val), le(_le), ri(_ri), pos(_pos) {}
};int lowbit(int x){return x & -x;
}template<class T>
struct fenwick{int n;vector<T> c;fenwick() {}fenwick(int _n): n(_n){c.resize(n + 1);}fenwick(const vector<T> &a): n(a.size()){c.resize(n + 1);for(int i = 1; i <= n; i++){c[i] = c[i] + a[i - 1];int j = i + lowbit(i);if(j <= n) c[j] = c[j] + c[i];}}void add(int x, const T& v){for(int i = x + 1; i <= n; i += lowbit(i)) c[i] = c[i] + v;}T ask(int x){T ans{};for(int i = x + 1; i; i -= lowbit(i)) ans = ans + c[i];return ans;}T ask(int l, int r){return ask(r) - ask(l - 1);}
};signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m;cin >> n >> m;vector<int> a(n), nums;vector<Node> tasks, tmp;for (int i = 0; i < n; i++) {cin >> a[i];nums.push_back(a[i]);tasks.emplace_back(1, a[i], -1, -1, i);}vector<vector<int>> g(n);for (int i = 0, u, v; i < n - 1; i++) {cin >> u >> v, u--, v--;g[u].push_back(v);g[v].push_back(u);}vector<int> dep(n);vector<int> par(n), siz(n), son(n, -1);auto dfs = [&](auto&& self, int u, int fa) -> void {siz[u] = 1, par[u] = fa;for (auto v : g[u]) {if (v == fa) continue;dep[v] = dep[u] + 1;self(self, v, u);siz[u] += siz[v];if (son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v;}};int clock = 0;vector<int> dfn(n), top(n);auto dfs2 = [&](auto&& self, int u, int topf) -> void {dfn[u] = clock++;top[u] = topf;if (~son[u]) self(self, son[u], topf);for (auto v : g[u]) {if (v == par[u] || v == son[u]) continue;self(self, v, v);}};dfs(dfs, 0, 0);dfs2(dfs2, 0, 0);fenwick<int> f(n);auto add = [&](int x, int y) { f.add(dfn[x], y); };auto ask = [&](int u, int v) {int ans = 0;while (top[u] != top[v]) {if (dep[top[u]] < dep[top[v]]) swap(u, v);ans += f.ask(dfn[top[u]], dfn[u]);u = par[top[u]];}if (dep[u] > dep[v]) swap(u, v);ans += f.ask(dfn[u], dfn[v]);return ans;};auto lca = [&](int u, int v) {while (top[u] != top[v]) {if (dep[top[u]] < dep[top[v]]) swap(u, v);u = par[top[u]];}if (dep[u] > dep[v]) swap(u, v);return u;};auto dist = [&](int u, int v) {return dep[u] + dep[v] - 2 * dep[lca(u, v)];	};int q = 0;for (int i = 0, k; i < m; i++) {cin >> k;if (k > 0) {int l, r;cin >> l >> r;l--, r--;tasks.emplace_back(0, k, l, r, q++);}else {int p, v;cin >> p >> v;p--;tasks.emplace_back(-1, a[p], -1, -1, p);tasks.emplace_back(1, v, -1, -1, p);nums.push_back(v);a[p] = v;}}sort(nums.begin(), nums.end());nums.erase(unique(nums.begin(), nums.end()), nums.end());vector<int> ans(q);for (auto &task : tasks) {if (task.tp == 0) {int len = dist(task.le, task.ri) + 1;if (task.val < 1 || task.val > len) ans[task.pos] = -1;else task.val = len - task.val + 1;continue;}int p = lower_bound(nums.begin(), nums.end(), task.val) - nums.begin();task.val = p;}auto solve = [&](auto &&self, int l, int r, int lo, int hi) -> void {if (l >= r) {return;}if (lo == hi) {for (int i = l; i <= r; i++) {if (tasks[i].tp == 0 && ans[tasks[i].pos] != -1) {ans[tasks[i].pos] = lo;}}return;}int mid = (lo + hi) / 2;vector<Node> tl, tr;for (int i = l; i <= r; i++) {if (tasks[i].tp) {if (tasks[i].val <= mid) {add(tasks[i].pos, tasks[i].tp);tl.push_back(tasks[i]);}else {tr.push_back(tasks[i]);}}else {int cnt = ask(tasks[i].le, tasks[i].ri);if (cnt >= tasks[i].val) {tl.push_back(tasks[i]);}else {tasks[i].val -= cnt;tr.push_back(tasks[i]);}}}for (int i = l; i <= r; i++) {if (tasks[i].tp && tasks[i].val <= mid) {add(tasks[i].pos, -tasks[i].tp);}}copy(tl.begin(), tl.end(), tasks.begin() + l);copy(tr.begin(), tr.end(), tasks.begin() + l + tl.size());self(self, l, l + tl.size() - 1, lo, mid);self(self, l + tl.size(), r, mid + 1, hi);};solve(solve, 0, tasks.size() - 1, 0, nums.size() - 1);for (int i = 0; i < q; i++) {if (ans[i] != -1) {cout << nums[ans[i]] << '\n';}else cout << "invalid request!" << '\n';}return 0;
}