题面
题解
题面很清楚
问题是要怎么做
其实就是查询一个动态集合的第 (k) 大
每次合并就把两个集合黏在一起就行了
我们可以想到用 splay 来写, 启发式合并一下就行
还有一种思路是权值线段树合并
每一次连边就相当于是一次合并
好像确实没有什么很难想的地方, 思路很顺啊
就是线段树合并的复杂度实在是不会分析
这里给出两种方式的代码
Code
splay
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 100005;
using namespace std;
int n, m, q, pa[N], rt[N];
struct Tree { int ch[2], fa, sz, val; } t[N];
char s[15];
template < typename T >
inline T read()
{
T x = 0, w = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * w;
}
int getf(int x) { return pa[x] ^ x ? pa[x] = getf(pa[x]) : x; }
void pushup(int p) { t[p].sz = t[t[p].ch[0]].sz + t[t[p].ch[1]].sz + 1; }
void rotate(int x)
{
int y = t[x].fa, z = t[y].fa, k = t[y].ch[1] == x;
t[z].ch[t[z].ch[1] == y] = x, t[x].fa = z;
t[y].ch[k] = t[x].ch[k ^ 1], t[t[x].ch[k ^ 1]].fa = y;
t[x].ch[k ^ 1] = y, t[y].fa = x;
pushup(y), pushup(x);
}
void splay(int x, int goal)
{
while(t[x].fa != goal)
{
int y = t[x].fa, z = t[y].fa;
if(z != goal)
(t[y].ch[1] == x) ^ (t[z].ch[1] == y) ? rotate(x) : rotate(y);
rotate(x);
}
}
void insert(int x, int u)
{
splay(u, 0); int ff = 0;
while(u)
ff = u, u = t[u].ch[t[x].val > t[u].val];
t[x].ch[0] = t[x].ch[1] = 0, t[x].sz = 1, t[x].fa = ff;
if(ff) t[ff].ch[t[x].val > t[ff].val] = x;
splay(x, 0);
}
void modify(int u, int fa)
{
if(!u) return;
modify(t[u].ch[0], fa);
modify(t[u].ch[1], fa);
insert(u, fa);
}
void merge(int u, int v)
{
u = getf(u), v = getf(v);
splay(u, 0), splay(v, 0);
if(t[u].sz < t[v].sz) swap(u, v);
modify(v, u);
}
void output(int u)
{
if(!u) return;
output(t[u].ch[0]);
printf("%d ", u);
output(t[u].ch[1]);
}
int kth(int x, int y)
{
int u = getf(x); splay(u, 0);
if(t[u].sz < y) return -1;
while(u)
{
if(y <= t[t[u].ch[0]].sz)
u = t[u].ch[0];
else if(y > t[t[u].ch[0]].sz + 1)
y -= t[t[u].ch[0]].sz + 1, u = t[u].ch[1];
else return u;
}
}
int main()
{
n = read <int> (), m = read <int> ();
for(int i = 1; i <= n; i++)
t[i].val = read <int> (), t[i].sz = 1, pa[i] = i;
for(int u, v, i = 1; i <= m; i++)
{
u = getf(u = read <int> ()), v = getf(v = read <int> ());
if(u == v) continue;
merge(u, v), pa[getf(v)] = getf(u);
}
q = read <int> ();
int x, y;
while(q--)
{
scanf("%s", s + 1), x = read <int> (), y = read <int> ();
if(s[1] == 'B')
{
x = getf(x), y = getf(y);
if(x == y) continue;
merge(x, y), pa[getf(y)] = getf(x);
}
if(s[1] == 'Q')
printf("%d
", kth(x, y));
}
return 0;
}
/*
7 3
1 3 6 2 5 7 4
1 4
4 7
4 6
4
B 2 3
B 2 5
B 5 4
Q 4 2
*/
我没写 else 调了一个多小时(滑稽
线段树合并
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 100005;
using namespace std;
int n, m, q, pa[N], rt[N], cnt;
struct Tree { int l, r, sz, id; } t[N * 32];
char s[15];
template < typename T >
inline T read()
{
T x = 0, w = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * w;
}
int getf(int x) { return pa[x] ^ x ? pa[x] = getf(pa[x]) : x; }
void modify(int &p, int l, int r, int k, int x)
{
p = ++cnt; t[p].sz++;
if(l == r)
return (void) (t[p].id = x);
int mid = (l + r) >> 1;
if(k <= mid) modify(t[p].l, l, mid, k, x);
else modify(t[p].r, mid + 1, r, k, x);
}
int merge(int p, int o, int l, int r)
{
if(!p || !o) return p + o;
t[p].sz += t[o].sz;
if(l == r)
return t[p].id = t[p].id + t[o].id, p;
int mid = (l + r) >> 1;
t[p].l = merge(t[p].l, t[o].l, l, mid);
t[p].r = merge(t[p].r, t[o].r, mid + 1, r);
return p;
}
int query(int p, int l, int r, int k)
{
if(l == r)
return t[p].id;
int mid = (l + r) >> 1, sum = t[t[p].l].sz;
if(k <= sum) return query(t[p].l, l, mid, k);
else return query(t[p].r, mid + 1, r, k - sum);
}
int main()
{
n = read <int> (), m = read <int> ();
for(int x, i = 1; i <= n; i++)
pa[i] = i, x = read <int> (), modify(rt[i], 1, n, x, i);
for(int u, v, i = 1; i <= m; i++)
{
u = getf(u = read <int> ()), v = getf(v = read <int> ());
if(u == v) continue;
rt[u] = merge(rt[u], rt[v], 1, n), pa[getf(v)] = getf(u);
}
q = read <int> ();
int x, y;
while(q--)
{
scanf("%s", s + 1), x = read <int> (), y = read <int> ();
if(s[1] == 'B')
{
x = getf(x), y = getf(y);
if(x == y) continue;
merge(rt[x], rt[y], 1, n), pa[getf(y)] = getf(x);
}
if(s[1] == 'Q')
{
printf("%d
", t[rt[getf(x)]].sz < y ? -1 : query(rt[getf(x)], 1, n, y));
}
}
return 0;
}
超级好写, 一下就写完了