题目链接
【洛谷】
【BZOJ】没有权限号嘤嘤嘤。题号:3545
题解
窝不会克鲁斯卡尔重构树怎么办???
可以离线乱搞。
我们将所有的操作全都存下来。
为了解决小于等于\(x\)的操作,那么我们按照长度来排一个序。
如果询问和加边长度相同,这加边优先。
对于每一个连通块进行权值线段树。
权值线段树解决\(k\)大的问题。
每一次合并,并查集判联通,线段树暴力合并。
时间复杂度\(O(nlogn)\)。
代码
#include <bits/stdc++.h>
using namespace std;
namespace IOstream {
#define gc getchar
template <typename T>
inline void read(T &x) {
x = 0; T fl = 1; char c = 0;
for (; c < '0' || c > '9'; c = gc())
if (c == '-') fl = -1;
for (; c >= '0' && c <= '9'; c = gc())
x = (x << 1) + (x << 3) + (c ^ 48);
x *= fl;
}
#undef gc
} using namespace IOstream;
int n, m, q;
const int N = 100000 + 5;
int val[N], id[N];
namespace seg {
#define ls(x) tr[x].lc
#define rs(x) tr[x].rc
struct node {
int lc, rc, s; node() { lc = rc = s = 0; }
} tr[N * 50];
int tot = 0;
void upd(int &k, int l, int r, int val) {
if (!k) k = ++ tot;
tr[k].s = 1;
if (l == r) return;
int mid = (l + r) >> 1;
if (val <= mid) upd(ls(k), l, mid, val);
else upd(rs(k), mid + 1, r, val);
}
int kth(int k, int l, int r, int rk) {
if (l == r) return l;
int mid = (l + r) >> 1;
if (rk <= tr[ls(k)].s) return kth(ls(k), l, mid, rk);
else return kth(rs(k), mid + 1, r, rk - tr[ls(k)].s);
}
int merge(int x, int y) {
if (!x || !y) return x + y;
if (!ls(x) && !rs(x)) { tr[x].s += tr[y].s; return x; }
ls(x) = merge(ls(x), ls(y));
rs(x) = merge(rs(x), rs(y));
tr[x].s = tr[ls(x)].s + tr[rs(x)].s;
return x;
}
}
struct ASK {
int a, b, c, d, id;
} Q[N * 10];
int fa[N], rt[N], ans[5 * N];
bool cmp_ASK(ASK A, ASK B) {
return A.c == B.c ? A.d < B.d : A.c < B.c;
}
int gf(int x) {
return x == fa[x] ? fa[x] : fa[x] = gf(fa[x]);
}
signed main() {
read(n); read(m); read(q);
for (int i = 1; i <= n; i ++) read(val[i]), id[i] = val[i], fa[i] = i;
sort(id + 1, id + 1 + n);
for (int i = 1; i <= n; i ++)
val[i] = lower_bound(id + 1, id + 1 + n, val[i]) - id;
for (int i = 1; i <= m; i ++)
read(Q[i].a), read(Q[i].b), read(Q[i].c), Q[i].d = 0;
for (int i = m + 1; i <= m + q; i ++)
read(Q[i].a), read(Q[i].c), read(Q[i].b), Q[i].d = 1, Q[i].id = i - m;
sort(Q + 1, Q + 1 + m + q, cmp_ASK);
for (int i = 1; i <= n; i ++) seg::upd(rt[i], 1, n, val[i]);
for (int i = 1; i <= m + q; i ++) {
if (!Q[i].d) {
int x = gf(Q[i].a), y = gf(Q[i].b);
if (x != y) {
fa[x] = y;
rt[y] = seg::merge(rt[x], rt[y]);
}
} else {
int x = gf(Q[i].a);
if (seg::tr[rt[x]].s < Q[i].b) ans[Q[i].id] = -1;
else ans[Q[i].id] = id[seg::kth(rt[x], 1, n, seg::tr[rt[x]].s - Q[i].b + 1)];
}
}
for (int i = 1; i <= q; i ++) printf("%d\n", ans[i]);
return 0;
}