Description

太长了懒得放

Input

输入文件galaxy.in的第一行有一个整数T（1<=T<=500,000），表示总共有T条指令。 以下有T行，每行有一条指令。指令有两种格式： M i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。 C i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。

Output

输出文件为galaxy.out。你的程序应当依次对输入的每一条指令进行分析和处理： 如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息； 如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i 号战舰与第j 号战舰之间布置的战舰数目。如果第i 号战舰与第j号战舰当前不在同一列上，则输出-1。

Solution

感觉自己带权并查集还不熟，于是做了一下这道很老的题。。。 我们除了记

TeX parse error: Undefined control sequence \[

表示x的祖先之外，还需要记

TeX parse error: Undefined control sequence \[

分别表示x到祖先的距离和x这个并查集的大小，然后直接维护即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 30000 + 100;
int fa[Maxn], Sum[Maxn], Dis[Maxn];
int N;
inline char safe_read()
{
    char ch = getchar();
    while (ch != 'M' && ch != 'C')ch = getchar();
    return ch;
}
inline int find (int x)
{
    if (fa[x] != x)
    {
        int k = fa[x];
        fa[x] = find(fa[x]);
        Dis[x] += Dis[k];
        Sum[x] = Sum[fa[x]];
    }
    return fa[x];
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    scanf("%d", &N);
    for (int i = 1; i <= Maxn; ++i)
        fa[i] = i, Sum[i] = 1;
    while (N --)
    {
        char type;
        int x, y;
        type = safe_read();
        scanf("%d%d", &x, &y);
        if (type == 'M')
        {
            int fx = find(x), fy = find(y);
            fa[fx] = fy;
            Dis[fx] = Dis[fy] + Sum[fy];
            Sum[fy] += Sum[fx];
            Sum[fx] = Sum[fy];
        }
        else 
        {
            int fx = find(x), fy = find(y);
            if (fx != fy)
                puts("-1");
            else 
            {
                printf("%d\n", abs(Dis[x] - Dis[y]) - 1);
            }
        }
    }
    return 0;
}