题目：https://www.luogu.org/problemnew/show/P1196
题意：有好多好多舰队排成一排。
M i，j表示将编号i舰队所在的列排到编号j舰队所在列的后面。
C i，j表示查询编号i舰队和编号j舰队如果在一列，中间间隔了多少只舰，如果不在同一列输出-1
思路：
很自然能想到用一个数组可以表示某一个舰排在这一列的第几个
当要查询的时候只需要用并查集查一下队首相不相同，然后把他们在队伍中的编号减一下就行。
因为要知道排在第几个，合并的时候因为是放在队尾，所以合并的时候就需要知道前面这个队伍原来的大小
所以还需要一个数组来维护队伍的大小。
剩下来就交给并查集来操作。
路径压缩的时候要把父亲的排名也加到自己身上。然后所在队伍的大小也要更新。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<map> 4 #include<set> 5 #include<cstring> 6 #include<algorithm> 7 #include<vector> 8 #include<cmath> 9 #include<stack> 10 #include<queue> 11 #include<iostream> 12 13 #define inf 0x7fffffff 14 using namespace std; 15 typedef long long LL; 16 typedef pair<string, string> pr; 17 18 int t; 19 const int maxn = 3e4 + 5; 20 int par[maxn], rnk[maxn], num[maxn]; 21 22 int ffind(int x) 23 { 24 if(par[x] == x)return x; 25 int tmp = par[x]; 26 par[x] = ffind(par[x]); 27 rnk[x] += rnk[tmp]; 28 num[x] = num[par[x]]; 29 return par[x]; 30 } 31 32 void init() 33 { 34 for(int i = 0; i < maxn; i++){ 35 par[i] = i; 36 rnk[i] = 0; 37 num[i] = 1; 38 } 39 } 40 41 void uunion(int x, int y) 42 { 43 int fx = ffind(x), fy = ffind(y); 44 par[fx] = fy; 45 rnk[fx] += num[fy]; 46 num[fx] += num[fy]; 47 num[fy] = num[fx]; 48 } 49 50 int main() 51 { 52 scanf("%d", &t); 53 init(); 54 for(int i = 0; i < t; i++){ 55 char type; 56 int x, y; 57 //getchar(); 58 cin>>type; 59 scanf("%d %d", &x, &y); 60 if(type == 'M'){ 61 uunion(x, y); 62 } 63 else{ 64 int fx = ffind(x), fy = ffind(y); 65 if(fx != fy){ 66 printf("-1 "); 67 } 68 else{ 69 //cout<<cnt[x]<<endl<<cnt[y]<<endl; 70 printf("%d ", abs(rnk[x] - rnk[y]) - 1); 71 } 72 } 73 } 74 return 0; 75 }