[NOI2002] 银河英雄传说

题目链接- [NOI2002] 银河英雄传说

题目背景

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

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

题目描述

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

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

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

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

输入格式

第一行有一个整数 T1 \le T \le 5 \times 10^5),表示总共有 T 条指令。

以下有 T 行,每行有一条指令。指令有两种格式:

  1. M i jij 是两个整数(1 \le i,j \le 30000),表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令,并且保证第 i 号战舰与第 j 号战舰不在同一列。
  2. C i jij 是两个整数(1 \le i,j \le 30000),表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。
输出格式

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

  • 如果是杨威利发布的舰队调动指令,则表示舰队排列发生了变化,你的程序要注意到这一点,但是不要输出任何信息。
  • 如果是莱因哈特发布的询问指令,你的程序要输出一行,仅包含一个整数,表示在同一列上,第 i 号战舰与第 j 号战舰之间布置的战舰数目。如果第 i 号战舰与第 j 号战舰当前不在同一列上,则输出 -1
样例 #1
样例输入 #1
4
M 2 3
C 1 2
M 2 4
C 4 2
样例输出 #1
-1
1
提示
样例解释

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

分析

很容易想到题目是并查集,但是这个权值比较有意思,这次我们将深入理解带权并查集。
目标是求出在当前时刻i战舰与j战舰之间的距离,而每次合并只将第一列的头接到第二列的尾上,其实这是利于迭代更新权值的。
这个距离该怎么求呢,保存一个该点到队头的距离,计算起来就是abs(dis[i]-dis[j])-1。但是每次合并的时候,我们无法把第一列的所有元素都更新一遍,这就像线段树不加Lazy-Tag,在路径压缩的时候,递归传递一个tag更新权值,大大减小时间复杂度。
这个权值该怎么保存呢?我们可以想到,既然我已经知道到当前队头的距离,而我的队头以及父亲都是fa[pos],那么我只要再保存一个队列体积,在合并时,将第二条队列的体积加到第一条队列的队头上,然后在查询时,由于队头的数据始终是最新的,最终把当前到队头的距离加上队头到路径压缩之后的队头的长度,这些都可以在递归中完成。

实现&细节

1.开一个dis数组,表示posfa[pos]的距离,开一个numb数组,表示当前队列的体积。
2.find函数,在每次查找的时候先保存好当前父亲的编号,在递归完成之后更新该点的距离,可以推理出递归的有效性。
3.merge函数,在合并前更新fax的距离,合并之后更新fay的体积,并清零fax的体积。

AC Code

#include
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int MAXN = 3e4 + 10;
int T, x, y;
char q;
int fa[MAXN], dis[MAXN], numb[MAXN];//dis为到队头的距离
/*需要两个参数,一个是到fa的距离,还有一个是当前块的体积*/
inline void init() {
  for(int i = 1; i <= 3e4; i++) {
    fa[i] = i;
    dis[i] = 0;
    numb[i] = 1;
  }
}
int find(int pos) {
  if(fa[pos] == pos) return pos;
  int fpos = find(fa[pos]);
  dis[pos] += dis[fa[pos]];
  return fa[pos] = fpos;
}
inline void merge(int posx, int posy) {
  int fax = find(posx);
  int fay = find(posy);
  if(fax != fay) {
    fa[fax] = fay, dis[fax] += numb[fay], numb[fay] += numb[fax], numb[fax] = 0;
  }
}
int main()
{
  std::ios::sync_with_stdio(false);//用了这个在linux上就不能用printf和scanf了
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  cin >> T;
  init();
  while(T--) {
    cin >> q >> x >> y;
    if(q == 'M') {
      merge(x, y);
    }
    if(q == 'C') {
      if(find(x) == find(y)) {
        cout << abs(dis[x] - dis[y]) - 1 << endl;
      }
      else cout << -1 << endl;
    }
  }
  return 0;
}