蒟蒻Sulfur6在第一次看见这道题的时候感觉它好水啊，然后五分钟打了个自以为是的正解。。肯定是错的太离谱了，那天晚上的代码带崩了我的三个系统。。。

刚刚学习并查集的时候就见过那个题，当时连最水的家族都做不出，真的是连题面都没看就跳过去了。

题目大意

给定一个最多有30000艘船的船队，初始状态一字排开。 接下来你要读入 T T 个指令 (1≤T≤5000001 \leq T \leq 500000)： 若为MijM i j，则将ii所在的舰队移动到jj所在舰队的后面（即将第ii艘舰船所在的战舰队列全部移动到第jj列舰船所在战舰队列的后面）； 若为CijC i j，如果第i,ji,j艘舰船在同一列中，则输出它们中间有的舰船数，如果不在同一列中，则输出−1-1。

这里要注意的是（可能只有我一个人这么智障），就是给定合并操作的iji j可能只是一列舰船中间或末尾的那个，不一定就是某列舰船的第一个。【天真的以为一定给定第一艘的蒟蒻就这么WA挺了。

压缩路径

  • 分析完题目大意之后我们会自然而然的想到一种做法，那就是记录每一列舰船所在的位置
  • 但是这样显然不靠谱，因为不路径压缩的UFS会爆炸。
  • 怎么在压缩路径的基础上维护战舰所在位置的信息呢？

    某优化

    如果说大家和我一样记得并查集路径压缩的代码的话，我们会发现，在路径压缩之前并没有维护什么信息，所以我们尝试着来搞一些事情
int a[MAXN];//某列战舰现有的战舰数，初始化为1
int b[MAXN];/*某列战舰现在在本列战舰内的深度，初始化为0*/
int fa[MAXN];//UFS中用的father数组
int find (int x) {
    int t;
    if (x != fa[x]) {
        t = find(fa[x]);
        b[x] += b[fa[x]];//这一句包括上面一句类似于递归求解确定x战舰在本列中的位置
        fa[x] = t;
    }
    return fa[x];
}

完整代码

#include <cstdio>
#include <cstdlib>
const int maxn = 30000;
const int maxt = 500000;
int fa[maxn + 5], a[maxn + 5], b[maxn + 5];
int ans;
int find (int x) {
    int t;
    if (x != fa[x]) {
        t = find(fa[x]);
        b[x] += b[fa[x]];
        fa[x] = t;
    }
    return fa[x];
}
int T;
int main () {
    scanf("%d", &T);
    for (int i = 1; i <= maxn + 1; i++) {
        fa[i] = i;
        a[i] = 1;
    }
    char c; int x, y;
    while (T--) {
        scanf("\n%c %d %d", &c, &x, &y);
        int f1 = find(x); int f2 = find(y);
        if (c == 'M') {//合并操作
            fa[f1] = f2;//修改战舰头
            b[f1] = a[f2];//修改战舰层数
            a[f2] += a[f1];//增加合并后该列的战舰数
        } else {
            if (f1 == f2) {
                ans = abs(b[x] - b[y]) - 1;//这里要记得-1，因为编号从0开始
                printf("%d\n", ans);
            } else printf("-1\n");
        }
    }
    
    return 0;
}

看这个难度也知道是NOI的一道水题，毕竟我这样的蒟蒻都能A。。 当年看着唐氏Pascal学并查集就死活学不会了，思想都不懂，这里要感谢教会我并查集的神犇Menci和Gty.