银河英雄传说

边带权并查集用于维护相互连通的结点之间的权值。其中的难点在于分析路径压缩时对于结点的更新。

在分析一道题时，我们要清楚自己所要得到的信息，并找到其来源。在写程序之前，先分析确定边权（深度？子树大小？），再分析回溯过程中权值的更新方式。

这道题带来的困惑是，对于合并队伍，我们会把树根连在一起。对于连通性显然是没有影响的，但是我们丧失了被合并的队伍队首以下的距离。如果我们记录每个结点到父结点的距离呢？在合并时X的所有结点更新，似乎太浪费时间了，并且由于并查集由下向上传递，在查的时候我们无法找到子结点，因而这种方法不可取。

我们希望在合并的时候只改变X的树根的权值。我们可以用d[x]表示结点到父结点之间的距离。由于题目询问集合中元素的数量，我们需要size[x]维护字数大小，并不断更新。这样一来，在合并的时候，我们可以把Y字数大小叠加到X的d中，表示X与Y之间相隔了d[x]的距离，再把X的子树大小叠加到Y中。在路径压缩时，把距父结点的权值不断由上到下叠加得到。

题目

公元五八○一年，地球居民迁至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。

宇宙历七九九年，银河系的两大军事集*在巴米利恩星域爆发战争。泰山压顶集**宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集*点名将杨威利组织麾下三万艘战舰迎敌。

杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成300003000030000列，每列依次编号为1,2,…,300001, 2, …,300001,2,…,30000。之后，他把自己的战舰也依次编号为1,2,…,300001, 2, …, 300001,2,…,30000，让第iii号战舰处于第iii列(i=1,2,…,30000)(i = 1, 2, …, 30000)(i=1,2,…,30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为Mi,jM_{i,j}Mi,j，含义为第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。

然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。

在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：Ci,jC_{i,j}Ci,j。该指令意思是，询问电脑，杨威利的第iii号战舰与第jjj号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。

作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。

最终的决战已经展开，银河的历史又翻过了一页……

输入输出格式

输入格式：

第一行有一个整数T(1≤T≤500,000)T(1 le T le 500,000)T(1≤T≤500,000)，表示总共有TTT条指令。

以下有TTT行，每行有一条指令。指令有两种格式：

Mi,jM_{i,j}Mi,j ：iii和jjj是两个整数(1≤i,j≤30000)(1 le i,j le 30000)(1≤i,j≤30000)，表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第iii号战舰与第jjj号战舰不在同一列。

Ci,jC_{i,j}Ci,j ：iii和jjj是两个整数(1≤i,j≤30000)(1 le i,j le 30000)(1≤i,j≤30000)，表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。

输出格式：

依次对输入的每一条指令进行分析和处理：

如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；

如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第iii号战舰与第jjj号战舰之间布置的战舰数目。如果第iii号战舰与第jjj号战舰当前不在同一列上，则输出−1-1−1。

CODE

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int SIZE = 30005;
 5 int fa[SIZE], d[SIZE], size[SIZE], t; //d记录到父节点距离 size记录子树大小 
 6 int get(int x){
 7     if(x == fa[x]) return x;
 8     int root = get(fa[x]);
 9     d[x] += d[fa[x]];
10     return fa[x] = root;
11 }
12 
13 void merge(int x, int y){
14     x = get(x), y = get(y);
15     fa[x] = y;
16     d[x] += size[y]; 
17     size[y] += size[x];
18     return;
19 }
20 
21 int main(){
22 //    freopen("galaxy1.in", "r", stdin);
23     cin >> t;
24     for(int i=1; i<SIZE; i++){
25         fa[i] = i;
26         d[i] = 0;
27         size[i] = 1;
28     } 
29     
30     while(t--){
31         char f;
32         int x, y;
33         scanf("
%c %d %d", &f, &x, &y);
34         switch(f){
35             case 'M':
36                 merge(x, y);
37                 break;
38             case 'C':
39                 if(get(x) != get(y)){
40                     printf("%d
", -1);
41                     continue;
42                 } 
43                 int ans = d[x] - d[y];
44                 ans = ans < 0 ? -ans : ans;
45                 printf("%d
", ans - 1);
46                 break;
47         }        
48         
49     }
50     return 0;
51 }

输入输出格式

相关推荐