题解 – P1196 [NOI2002] 银河英雄传说

[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 号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。

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

输入格式

第一行有一个整数 T（1 \le T \le 5 \times 10^5），表示总共有 T 条指令。

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

1. M i j：i 和 j 是两个整数（1 \le i,j \le 30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第 i 号战舰与第 j 号战舰不在同一列。
2. C i j：i 和 j 是两个整数（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数组，表示pos到fa[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;
}