题解 P3224 [HNOI2012]永无乡
2021/8/12 23:07:16
本文主要是介绍题解 P3224 [HNOI2012]永无乡,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
前置知识:kruskal 重构树,主席树
来讲一种目前题解区里没有,使用 kruskal 重构树和主席树,且时间复杂度为一个 log 的做法。
题目大意是给定一张点数为 \(n\) ,初始边数为 \(m\) 的无向图,图中每个点有一个权值,然后有 \(q\) 个操作,每个操作可能是询问与点 \(x\) 联通的点中权值第 \(k\) 小的点的编号,也可能是加入一条无向边。
看到这种与联通性相关的题,自然能想到 kruskal 重构树,于是把操作离线,连边操作直接丢给 kruskal 重构树,把其对应点的限制设为时间戳,然后将询问操作也带上时间戳存下来。
这样我们就解决了动态加边的问题,再给 kruskal 重构树加个倍增,我们就可以快速得到一个询问所对应的点集了。
询问的是第 \(k\) 小,于是在 kruskal 重构树上再跑个 dfs 序,弄颗主席树,此题就做完啦 ^_^
时间复杂度:\(O(qlog(n))\)
此外,实现时有个坑点,这张图不一定联通,所以 dfs 时一定要把每个根都跑了。
参考代码:
#include <bits/stdc++.h> #define rei register int #define ll long long using namespace std; const int inf = 0x3f3f3f3f; const int N = 1e5 + 5, M = 1e5 + 5, MAXQ = 3e5 + 5; int n, m, Q, tot, totq, num; int val[N * 2], fa[N * 2], f[N * 2][19], lim[N * 2]; int lson[N * 2], rson[N * 2], siz[N * 2]; int id[N * 2], key[N]; struct Segment_Tree { int tot, ver[N * 2]; struct node { int cnt, ls, rs; } T[N * 39]; int build(int l, int r) { int nnow = ++tot; if(l == r) return nnow; int mid = (l + r) >> 1; T[nnow].ls = build(l, mid); T[nnow].rs = build(mid + 1, r); return nnow; } int add(int x, int k, int l, int r, int now) { int nnow = ++tot; T[nnow] = T[now]; if(l == r) { T[nnow].cnt += k; return nnow; } int mid = (l + r) >> 1; int &L = T[nnow].ls, &R = T[nnow].rs; if(x <= mid) L = add(x, k, l, mid, T[now].ls); else R = add(x, k, mid + 1, r, T[now].rs); T[nnow].cnt = T[L].cnt + T[R].cnt; return nnow; } int ask(int k, int l, int r, int now1, int now2) { if(l == r) { return key[l]; } int L1 = T[now1].ls, R1 = T[now1].rs; int L2 = T[now2].ls, R2 = T[now2].rs; int mid = (l + r) >> 1; if(k <= T[L2].cnt - T[L1].cnt) { return ask(k, l, mid, L1, L2); } else { return ask(k - T[L2].cnt + T[L1].cnt, mid + 1, r, R1, R2); } } } SMT; int find(int x) { if(fa[x] == x) return x; return fa[x] = find(fa[x]); } void link(int u, int v, int l) { if(tot == 2 * n - 1) return; u = find(u), v = find(v); if(u == v) return; fa[u] = fa[v] = f[u][0] = f[v][0] = ++tot; fa[tot] = f[tot][0] = tot; lim[tot] = l, val[tot] = inf; lson[tot] = u, rson[tot] = v; } struct query { int x, k, high; query(int x = 0, int k = 0, int high = 0) { this->x = x, this->k = k, this->high = high; } } q[MAXQ]; void dfs(int x) { id[x] = ++num, siz[x] = 1; if(val[x] == inf) SMT.ver[num] = SMT.ver[num - 1]; else key[val[x]] = x, SMT.ver[num] = SMT.add(val[x], 1, 1, n, SMT.ver[num - 1]); if(lson[x]) dfs(lson[x]), siz[x] += siz[lson[x]]; if(rson[x]) dfs(rson[x]), siz[x] += siz[rson[x]]; } int solve(query pb) { int x = pb.x, k = pb.k, high = pb.high; for(rei i = 17; i >= 0; --i) { if(lim[f[x][i]] < high) { x = f[x][i]; } } int l = SMT.ver[id[x] - 1], r = SMT.ver[id[x] + siz[x] - 1]; if(k > SMT.T[r].cnt - SMT.T[l].cnt) return -1; return SMT.ask(k, 1, n, l, r); } int main() { ios::sync_with_stdio(false), cin.tie(NULL); cin >> n >> m; tot = n; for(rei i = 1; i <= n; ++i) { cin >> val[i]; fa[i] = f[i][0] = i; } for(rei i = 1; i <= m; ++i) { int u, v; cin >> u >> v; link(u, v, 0); } cin >> Q; for(rei i = 1; i <= Q; ++i) { char op; int x, y; cin >> op >> x >> y; if(op == 'B') { link(x, y, i); } else { q[++totq] = query(x, y, i); } } for(rei j = 1; j <= 17; ++j) { for(rei i = 1; i <= tot; ++i) { f[i][j] = f[f[i][j - 1]][j - 1]; } } SMT.ver[0] = SMT.build(1, n); for(rei i = 1; i <= tot; ++i) { if(fa[i] == i) dfs(i); } for(rei i = 1; i <= totq; ++i) { cout << solve(q[i]) << "\n"; } return 0; }
无耻求波赞 QAQ
这篇关于题解 P3224 [HNOI2012]永无乡的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)