【洛谷】AT_abc372_e [ABC372E] K-th Largest Connected Components 的题解
【洛谷】AT_abc372_e [ABC372E] K-th Largest Connected Components 的题解
题解
并查集，哦哦哦哦哦哦，刚开始看成最小生成树，然后又看成线段树qaq
看 @guozhetao 大佬，写了这篇题解，然后发现我刚好也水过这场比赛的 D 题的题解，刚好顺便切一下 E，然后来写一个题解。
题目每次有两种操作：
1 u v：将
u
u
u 和
v
v
v 合并。
2 v k：询问所有和
v
v
v 联通的点当中编号第
k
k
k 大的点。
首先，
k
k
k 的范围很小，所以我们可以直接用暴力维护，当然想用线段树也可以，实现两个连通块的合并时，把其中一个连通块中最大的前
10
10
10 个值用归并排序的方法合并到另一个连通块中并只取前
10
10
10 个值即可。查询的时候，直接找到这个点在哪个块内，然后查询相应值即可。时间复杂度
O
(
n
+
q
log
n
)
O(n+q \log n)
O(n+qlogn)。
代码
#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define endl "\n"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO {
inline int read() {
register int x = 0, f = 1;
register char c = getchar();
while (c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
inline void write(int x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
return;
}
}
using namespace fastIO;
int n, q, fa[200005], cnt[200005], ans[200005][25];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
bool cmp(int x, int y) {return x > y;}
int main() {
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n = read(), q = read();
for(int i = 1; i <= n; i ++) {
cnt[i] = 1;
fa[i] = i;
ans[i][1] = i;
}
while(q --) {
int op;
cin >> op;
if(op == 1) {
int u, v;
u = read(), v = read();
int fu = find(u), fv = find(v);
if(fu == fv) continue;
for(int i = 1; i <= cnt[fv]; i ++) {
ans[fu][i + cnt[fu]] = ans[fv][i];
}
sort(ans[fu] + 1, ans[fu] + cnt[fu] + cnt[fv] + 1, cmp);
for(int i = 11; i <= cnt[fu] + cnt[fv]; i ++) {
ans[fu][i] = 0;
}
cnt[fu] = min(cnt[fu] + cnt[fv], 10);
cnt[fv] = 0;
fa[fv] = fu;
}
else {
int v,k;
v = read(), k = read();
int fv = find(v);
if(k > cnt[fv]) {
write(-1), putchar('\n');
}
else {
write(ans[fv][k]), putchar('\n');
}
}
}
return 0;
}
原文地址：https://blog.csdn.net/ZH_qaq/article/details/142669453
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！