大意：你有30000个队列，第i个队列中只有i
有T个操作，1，把某个队列头接到另一个队列尾。
2，问两个元素之间的距离。
本题主要有三种解法。
①带权并查集。
具体来说就是，并查集维护当前集合的大小，这个点距离代表元(队首)的边数。
然后把合并和路径压缩魔改一下。询问的时候就直接取距离之差。
#include <cstdio> const int N = ; int fa[N], sum[N], siz[N];
char str[]; inline int find(int x, int &s) {
if(fa[x] == x) {
s = ;
return x;
}
int t = find(fa[x], s);
s += sum[x];
sum[x] = s;
return fa[x] = t;
} inline void merge(int x, int y) {
int a, b;
x = find(x, a);
y = find(y, b);
fa[x] = y;
sum[x] = siz[y];
siz[y] += siz[x];
return;
} inline int ask(int x, int y) {
int a, b;
x = find(x, a);
y = find(y, b);
if(x != y) {
return -;
}
return (a > b ? a - b : b - a) - ;
} int main() {
int n;
scanf("%d", &n);
for(int i = ; i <= ; i++) {
fa[i] = i;
siz[i] = ;
}
for(int i = , x, y; i <= n; i++) {
scanf("%s%d%d", str, &x, &y);
if(str[] == 'M') {
merge(x, y);
}
else {
printf("%d\n", ask(x, y));
}
} return ;
}
AC代码
②平衡树
这个太暴力了......开30000颗平衡树即可。
③离线(kruskal重构树)
重构的时候把顺序搞一下，然后提出来DFS序，直接回答询问。