洛谷P1196「NOI2002」题解

发表于 | 评论数： | 阅读次数：

带权并查集套队列好题。

题目描述

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

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

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

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

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

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

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

输入输出格式

输入格式

第一行有一个整数$T(1 \leq T \leq 500000)$,表示总共有$T$条指令。

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

  1. $M_{i,j}$，$i,j$是两个整数$1 \leq i,j \leq 30000$，表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第$i$号战舰与第$j$号战舰不在同一列。
  2. $C_{i,j}$,$i,j$是两个整数$1 \leq i,j \leq 30000$，表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。

输出格式

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

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

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

INPUT & OUTPUT’s examples

Input’s e.g. #1

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

Output’s e.g. #1

1
2
-1
1

说明

【样例说明】

战舰位置图：表格中阿拉伯数字表示战舰编号

explannition.png

分析

看到合并，查询操作，很自然地想到并查集（冰茶姬）。

我们把每一列的所有战舰看做一个集合，然后就可以用冰茶姬处理啦!

但这题和传统的并查集不太一样,我们需要求两艘战舰之间有多少艘战舰，也就是两艘战舰的距离。

所以考虑并查集套队列。

那么我们合并的时候，直接将一个队列的队头接在一个另一个队列的队尾即可。

因为题意中要求多次求两战舰之间的距离，那么可以考虑前缀和。

我们定义一个数组$anc[i]$来表示战舰$i$到其队头的距离，那么这样两个战舰$i,j$之间的距离就可以表示为
$|anc_i - anc_j|-1$。

那么，我们如何计算$anc[]$数组呢？

我们已经知道，在并查集合并的时候，改变的只是两个队头的祖先，而队列里其他战舰的祖先并没有被更新，仍然可以找到其原来的祖先（队头），所以在每次合并的时候，只要更新合并前队头到当前队头的距离即可，其他的则可通过这组数据即可。

对于任意一艘飞船，它到队头的距离就等于它到其祖先的距离加上其祖先到队头的距离，所以这样就可以递归下去。
我们得到$anc_i += anc[UFS[i]]$.

我们再开一个数组$num[i]$表示以$i$为队头的队列的飞船的数量，并初始化为1。

每次合并的时候，我们首先更新$anc$数组，即anc[Find(x)] += num[Find(y)].

然后开始合并，num[Find(y)] += Find(x)，然后num[x] = 0。

最后输出的时候要先判断一下是否在同一个队列里，然后按要求输出即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<iostream>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS() std::ios::sync_with_stdio(false); 
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*its=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==its)
            its=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==its)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        }
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x){
    FastIO::putint(x);
    FastIO::flush();
}
/* definitions */
const int MAXN = 3e4 + 1;
int UFS[MAXN];
int anc[MAXN],num[MAXN];
int T,ans;
/* functions */
inline void UFSinit(){
    FOR(i,0,MAXN,1){UFS[i] = i;num[i] = 1;}
}
inline int Find(int k){
    if(UFS[k] != k){
        int Temp = UFS[k];
        UFS[k] = Find(UFS[k]);
        anc[k] += anc[Temp];
        num[k] = num[UFS[k]];
    } 
    return UFS[k];
}
inline void unionx(int x,int y){
    int findx = Find(x);
    int findy = Find(y);
    if(findx != findy){
        UFS[findx] = findy;
        anc[findx] = anc[findy] + num[findy];
        num[findy] += num[findx];
        num[findx] = num[findy];
    }
}
inline int Query(int x,int y){
    if(Find(x)!=Find(y))return -1;
    if(Find(x)==Find(y))return std::abs(anc[x]-anc[y])-1;
}
int main(int argc,char *argv[]){
    UFSinit();
    std::cin>>T;
    while(T--){
        char op;
        int x,y;
        std::cin>>op>>x>>y;
        if(op=='M')unionx(x,y);
        else if(op=='C'){
            int ans = Query(x,y);
            std::cout<<ans<<std::endl;
        }
    }
    return 0;
}

THE END