題目描述

公元五八○一年，地球居民遷移至金牛座α第二行星，在那里發表銀河聯邦

創立宣言，同年改元為宇宙歷元年，并開始向銀河系深處拓展。

宇宙歷七九九年，銀河系的兩大軍事集團在巴米利恩星域爆發戰爭。泰山壓

頂集團派宇宙艦隊司令萊因哈特率領十萬余艘戰艦出征，氣吞山河集團點名將楊

威利組織麾下三萬艘戰艦迎敵。

楊威利擅長排兵布陣，巧妙運用各種戰術屢次以少勝多，難免恣生驕氣。在

這次決戰中，他將巴米利恩星域戰場劃分成30000列，每列依次編號為1, 2, …,

30000。之后，他把自己的戰艦也依次編號為1, 2, …, 30000，讓第i號戰艦處于

第i列(i = 1, 2, …, 30000)，形成“一字長蛇陣”，誘敵深入。這是初始陣形。當

進犯之敵到達時，楊威利會多次發布合并指令，將大部分戰艦集中在某幾列上，

實施密集攻擊。合并指令為M i j，含義為讓第i號戰艦所在的整個戰艦隊列，作

為一個整體（頭在前尾在后）接至第j號戰艦所在的戰艦隊列的尾部。顯然戰艦

隊列是由處于同一列的一個或多個戰艦組成的。合并指令的執行結果會使隊列增

大。 然而，老謀深算的萊因哈特早已在戰略上取得了主動。在交戰中，他可以通

過龐大的情報網絡隨時監聽楊威利的艦隊調動指令。

在楊威利發布指令調動艦隊的同時，萊因哈特為了及時了解當前楊威利的戰

艦分布情況，也會發出一些詢問指令：C i j。該指令意思是，詢問電腦，楊威利

的第i號戰艦與第j號戰艦當前是否在同一列中，如果在同一列中，那么它們之

間布置有多少戰艦。

作為一個資深的高級程序設計員，你被要求編寫程序分析楊威利的指令，以

及回答萊因哈特的詢問。

最終的決戰已經展開，銀河的歷史又翻過了一頁……

輸入輸出格式

輸入格式： 輸入文件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），表示指令涉及的戰艦編號。 該指令是萊因哈特發布的詢問指令。

輸出格式： 輸出文件為galaxy.out。你的程序應當依次對輸入的每一條指令進行分析和

處理：

如果是楊威利發布的艦隊調動指令，則表示艦隊排列發生了變化，你的程序

要注意到這一點，但是不要輸出任何信息；

如果是萊因哈特發布的詢問指令，你的程序要輸出一行，僅包含一個整數，

表示在同一列上，第i 號戰艦與第j 號戰艦之間布置的戰艦數目。如果第i 號戰

艦與第j號戰艦當前不在同一列上，則輸出-1。

輸入輸出樣例

輸入樣例#1： 4 M 2 3 C 1 2 M 2 4 C 4 2 輸出樣例#1： -1 1 說明

【樣例說明】

戰艦位置圖：表格中阿拉伯數字表示戰艦編號

分析： 這是去年在紀中做過的例題，就不解釋了

代碼：

include

include

include

include

using namespace std; const int maxn=30000+10;

int p[maxn],value[maxn],num[maxn]; int findset(int x,int &pson) { if(p[x]==x) { pson=x;return 0; } else { value[x]+=findset(p[x],p[x]); pson=p[x]; return value[x]; } }

void change(int x,int y) { int a ,b; findset(x,fx); findset(y,fy); p[fx]=fy; value[fx]=num[fy]; num[fy]+=num[fx]; num[fx]=0; }

void ask(int x,int y) { int fx,fy; findset(x,fx); findset(y,fy); if(fx!=fy)PRintf(“-1/n”); else printf(“%d/n”,abs(value[x]-value[y])-1); return ; }

int main() { int T;cin>>T; char ins[10]; int x,y; for(int i=1;i<=maxn-10;i++) p[i]=i,num[i]=1; while(T–) { scanf(“%s%d%d”,ins,&x,&y); if(ins[0]==’M’) change(x,y); else ask(x,y); } return 0; }