有一个划分为N列的星际战场，各列依次编号为1,2,…,N。

有N艘战舰，也依次编号为1,2,…,N,其中第i号战舰处于第i列。

有T条指令，每条指令格式为以下两种之一：

1、M i j，表示让第i号战舰所在列的全部战舰保持原有顺序，接在第j号战舰所在列的尾部。

2、C i j，表示询问第i号战舰与第j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。

现在需要你编写一个程序，处理一系列的指令。

输入格式

第一行包含整数T，表示共有T条指令。

接下来T行，每行一个指令，指令有两种形式：M i j或C i j。

其中M和C为大写字母表示指令类型，i和j为整数，表示指令涉及的战舰编号。

输出格式

你的程序应当依次对输入的每一条指令进行分析和处理：

如果是M i j形式，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；

如果是C i j形式，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目，如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。

数据范围

N≤30000,T≤500000N≤30000,T≤500000

输入样例：

4M 2 3C 1 2M 2 4C 4 2

输出样例：

-11

 

算法：带权并查集

带权并查集：普通的并查集是用一个f数组来记录前一个节点的位置，而带权并查集还需要用一个d数组来记录前面所以节点的总权值。

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn = 5e5+7;int f[maxn];int d[maxn];int size[maxn];int find(int x) {    if(x == f[x]) {        return f[x];    }    int root = find(f[x]);    d[x] += d[f[x]];    //更新当前节点x前面的战舰数量    return f[x] = root;}int main() {    for(int i = 0; i <= maxn; i++) {        f[i] = i;        size[i] = 1;    }    int n;    scanf("%d", &n);    while(n--) {        char op[2];        int x, y;        scanf("%s%d%d", op, &x, &y);        int fx = find(x);        int fy = find(y);        if(op[0] == 'M') {            if(fx != fy) {                f[fx] = fy;        //将节点x接在节点y后面                d[fx] = size[fy];        //更新节点x前面的战舰数量                size[fy] += size[fx];        //更新此列以节点y为头节点的战舰总数量            }        } else {            if(fx == fy) {                printf("%d\n", (int)abs(d[x] - d[y]) - 1);            } else {                printf("-1\n");            }        }    }    return 0;}