【NOI2002】caioj1095: 并查集4（銀河英雄傳說）

1095: 并查集4（銀河英雄傳說）

2020年發現一隻沒過審，重新投了一下

時間限制: 1 Sec 記憶體限制: 128 MB

題目描述

【問題描述】

公元五八○一年，地球居民遷移至金牛座α第二行星，在那裡發表銀河聯邦創立宣言，同年改元為宇宙曆元年，并開始向銀河系深處拓展。

宇宙曆七九九年，銀河系的兩大jun事集團在巴米利恩星域爆發戰争。泰山壓頂集團派宇宙艦隊司令萊因哈特率領十萬餘艘戰艦出征， 氣吞山河集團點名将楊威利組織麾下三萬艘戰艦迎敵。

楊威利擅長排兵布陣，巧妙運用各種戰術屢次以少勝多，難免恣生驕氣。在這次決戰中，他将巴米利恩星域戰場劃分成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行，每行有一條指令。指令有兩種格式：

1. M i j ：i和 j是兩個整數（1<=i , j<=30000） ，表示指令涉及的戰艦編号。該指令是萊因哈特竊聽到的楊威利釋出的艦隊調動指令，并且保證第 i号戰艦與第 j号戰艦不在同一列。

2. C i j ：i和 j是兩個整數（1<=i , j<=30000） ，表示指令涉及的戰艦編号。該指令是萊因哈特釋出的詢問指令。

   【輸出檔案】

   輸出檔案為 galaxy.out。你的程式應當依次對輸入的每一條指令進行分析和處理：

   如果是楊威利釋出的艦隊調動指令，則表示艦隊排列發生了變化，你的程式要注意到這一點，但是不要輸出任何資訊； 如果是萊因哈特釋出的詢問指令，你的程式要輸出一行，僅包含一個整數，表示在同一列上，第 i 号戰艦與第 j 号戰艦之間布置的戰艦數目。如果第 i 号戰艦與第 j号戰艦目前不在同一列上，則輸出-1。

   【樣例輸入】

   4

   M 2 3

   C 1 2

   M 2 4

   C 4 2

   【樣例輸出】

   -1

   1

   

   題目廢話好多，，，關鍵可直接看樣例說明即可

第一想法很簡單，直接用并查集，求解數量就直接暴力求，測試一下過了樣例，然而後面點計數卻會逾時，（500000操作。。。）顯然要繼續改進

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int fa[30001];
int find(int x){
	if (fa[x]!=x) {
		fa[x]=find(fa[x]); 
	}
	return fa[x];
}
int main(){
	int t;
	scanf("%d",&t);
	for (int i=1;i<=30001;i++) fa[i]=i;
	for (int i=1;i<=t;i++){
		char p;int a,b;
		cin>>p;
		scanf("%d%d",&a,&b);
		if (p=='M') {
			fa[find(a)]=find(b);
			fa[a]=find(b);
		}	
		else{
			if (fa[a]==fa[b]){
				int s,minn,maxx;
				minn=min(a,b)+1;
				maxx=max(a,b);
				for(int j=minn;j<=maxx;j++){
					if (fa[j]==fa[a]) s++;
				} 
				printf("%d\n",s);
				s=0;
			}
			else{
				printf("-1\n");
			}
		}
	}
	for (int i=1;i<=4;i++) printf("%d ",fa[i]);
	return 0;
}
           

出現問題之後我們就，現在一起想想想,(當你碰到困難 想！想！想！(霧

或者我們可以考慮利用一個數組來記錄和維護一下數值是不是會友善一些呢？

這就好比是求兩點之間的距離問題，多次尋求距離時我們很容易就想到字首和，隻要abs（隊頭-隊尾）+1就可以求出距離

#include<bits/stdc++.h>
using namespace std;
int fa[30001],front[30001],num[30001],x,y,i,j,n,T,ans;    //fa[i]表示飛船i的祖先
//front[i]表示飛船i與其所在列隊頭的距離
                                        //num[i]表示第i列的飛船數量 
char ins;
int find(int n){                                        //查找祖先的函數 
    if(fa[n]==n)return fa[n];
    int fn=find(fa[n]);                                    //先遞歸找到祖先 
    front[n]+=front[fa[n]];    //在回溯的時候更新front（因為更新時要用到正确的front[祖先]，
                                    //是以隻能在回溯的時候更新） 
    return fa[n]=fn;
}
int main(){
    cin>>T;
    for(i=1;i<=30000;++i){                                //定初值 
        fa[i]=i;
        front[i]=0;
        num[i]=1;
    }
    while(T--){
        cin>>ins>>x>>y;
        int fx=find(x);                                    //fx為x所在列的隊頭 
        int fy=find(y);                                    //fy同上 
        if(ins=='M'){
            front[fx]+=num[fy];        //更新front[x所在列隊頭(現在在y所在隊列後面)]
//即加上y所在隊列的長度 
            fa[fx]=fy;                                    //将fy設為fx的祖先 
            num[fy]+=num[fx];                            //更新以fy為隊頭隊列的長度 
            num[fx]=0;                        //以fx為隊頭的隊列已不存在，更新 
        }
        if(ins=='C'){
            if(fx!=fy)cout<<"-1"<<endl;            //若x和y的祖先不相同，則不在同一列 
else cout<<abs(front[x]-front[y])-1<<endl;    //否則利用x和y離隊頭的距離算
//出它們的距離 
        }
    }
    return 0;
}
           

from洛谷題解，，，侵删

回頭再自己修改好