P3242 [HNOI2015] 接水果

給定一棵樹，定義給定了$p$個(gè)盤子，每個(gè)盤子是樹上$u,v$兩點(diǎn)的路徑，且盤子有權(quán)值，定義水果，水果也是樹上$u,v$兩點(diǎn)間的路徑。

有$q$個(gè)詢問，每次給定$u,v,k$，表示可以接住水果$u,v$的盤子中權(quán)值第$k$小的權(quán)值是什么，輸出權(quán)值，一個(gè)盤子可以接住一個(gè)水果，當(dāng)且僅當(dāng)盤子是水果的子路徑。

考慮如何求是否覆蓋，對(duì)每個(gè)點(diǎn)$dfs$序得到$[s{t}_i,e{d}_i]$，對(duì)于$(u,v),s{t}_u\le s{t}_v$，

• $lca(u,v)=u$，則只要有一個(gè)點(diǎn)$dfs$序在$[s{t}_v,e{d}_v]$，并且有一個(gè)點(diǎn)$dfs$序在$[1,s{t}_z?1],[e{d}_z+1,n]$，即為內(nèi)含，其中$z$為$u,v$路徑上$u$的兒子。
• $lca(u,v)=u$，則只要有一個(gè)點(diǎn)$dfs$序在$[s{t}_u,e{d}_u]$，并且有一個(gè)點(diǎn)$dfs$序在$[s{t}_v,e{d}_v]$，即為內(nèi)含。

可以把所有矩形的差分，類似掃描線離線一下，然后整體二分即可。

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int head[N], to[N << 1], nex[N << 1], cnt = 1;int son[N], dep[N], top[N], sz[N], st[N], ed[N], fa[N], tot;int ans[N], sum[N], n, P, Q, num;struct Res {int op, x, l, r, k, id;bool operator < (const Res &t) const {return x != t.x ? x < t.x : op < t.op;} }q[N * 5], q1[N * 5], q2[N * 5];inline int lowbit(int x) {return x & (-x); }void update(int rt, int v) {while (rt <= n) {sum[rt] += v;rt += lowbit(rt);} }int query(int rt) {int ans = 0;while (rt) {ans += sum[rt];rt -= lowbit(rt);}return ans; }void add(int x, int y) {to[cnt] = y;nex[cnt] = head[x];head[x] = cnt++; }void dfs1(int rt, int f) {fa[rt] = f, sz[rt] = 1, dep[rt] = dep[f] + 1, st[rt] = ++tot;for (int i = head[rt]; i; i = nex[i]) {if (to[i] == f) {continue;}dfs1(to[i], rt);sz[rt] += sz[to[i]];if (!son[rt] || sz[to[i]] > sz[son[rt]]) {son[rt] = to[i];}}ed[rt] = tot; }void dfs2(int rt, int tp) {top[rt] = tp;if (!son[rt]) {return ;}dfs2(son[rt], tp);for (int i = head[rt]; i; i = nex[i]) {if (to[i] == fa[rt] || to[i] == son[rt]) {continue;}dfs2(to[i], to[i]);} }int lca(int u, int v) {while (top[u] != top[v]) {if (dep[top[u]] < dep[top[v]]) {swap(u, v);}u = fa[top[u]];}return dep[u] < dep[v] ? u : v; }int get(int u, int v) {while (top[u] != top[v]) {if (fa[top[v]] == u) {return top[v];}v = fa[top[v]];}return son[u]; }void solve(int L, int R, int l, int r) {if (L > R) {return ;}if (l == r) {for (int i = L; i <= R; i++) {if (q[i].op == 2) {ans[q[i].id] = l;}}return ;}int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;for (int i = L; i <= R; i++) {if (q[i].op != 2) {if (q[i].k <= mid) {update(q[i].l, q[i].op), update(q[i].r + 1, -q[i].op);q1[++cnt1] = q[i];}else {q2[++cnt2] = q[i];}}else {int cur = query(q[i].l);if (cur >= q[i].k) {q1[++cnt1] = q[i];}else {q[i].k -= cur;q2[++cnt2] = q[i];}}}for (int i = 1; i <= cnt1; i++) {if (q1[i].op != 2) {update(q1[i].l, -q1[i].op), update(q1[i].r + 1, q1[i].op);}}for (int i = 1; i <= cnt1; i++) {q[L + i - 1] = q1[i];}for (int i = 1; i <= cnt2; i++) {q[L + cnt1 + i - 1] = q2[i];}solve(L, L + cnt1 - 1, l, mid), solve(L + cnt1, R, mid + 1, r); }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);scanf("%d %d %d", &n, &P, &Q);for (int i = 1, u, v; i < n; i++) {scanf("%d %d", &u, &v);add(u, v);add(v, u);}dfs1(1, 0);dfs2(1, 1);for (int i = 1, u, v, x; i <= P; i++) {scanf("%d %d %d", &u, &v, &x);if (st[u] > st[v]) {swap(u, v);}// u < v;int cur = lca(u, v);if (cur == u) {int z = get(u, v);// [1, st[z] - 1]if (st[z] != 1) {q[++num] = {1, 1, st[v], ed[v], x, 0};q[++num] = {-1, st[z], st[v], ed[v], x, 0};}// [ed[z] + 1, n]if (ed[z] != n) {q[++num] = {1, st[v], ed[z] + 1, n, x, 0};q[++num] = {-1, ed[v] + 1, ed[z] + 1, n, x, 0};}}else {q[++num] = {1, st[u], st[v], ed[v], x, 0};q[++num] = {-1, ed[u] + 1, st[v], ed[v], x, 0};}}for (int i = 1, u, v, k; i <= Q; i++) {scanf("%d %d %d", &u, &v, &k);if (st[u] > st[v]) {swap(u, v);}q[++num] = {2, st[u], st[v], 0, k, i};}sort(q + 1, q + 1 + num);solve(1, num, 0, 1000000000);for (int i = 1; i <= Q; i++) {printf("%d\n", ans[i]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P3242 [HNOI2015] 接水果（整体二分、扫描线）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。