<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
并查集
这个问题可以说是真正“全裸”的带权并查集问题,挨个分析“并”和“查”,以及路径压缩:
①先来看比较简单的“查”
位于同一列中的战舰$x,y$之间的间隔数,可以用它们和排头之间的间隔数($toHead$表给出)作差取绝对值得出,相隔战舰的数量在此基础上继续减去1就可得,其中如果两战舰是相同的战舰,那么它们之间战舰的数量当然是0,和间隔数为1的时候相同,这个分类讨论也可以用$max(0, abs(toHead[x]-toHead[y]) - 1)$简写,效果相同
②再来分析“并”操作
由上图可知,长度为$l_1$的源$(src)$队列并入长度为$l_2$的目标$(dest)$队列时,原$src$队列的排头已经不再是$src$而是$dest$了,因此$toHead[src]$要加上原先$dest$队列的长度$len[dest]=l_2$,然后将$len[dest]$更新为$l_1+l_2$
③最后分析一下路径压缩
此图中展示了常规的路径压缩之前,需要做什么事:查找到x的源之后,将原先$ori[x]$的间隔数$l_0$累加到x的间隔数上,然后再更新x的源,这样得出的$toHead[x]$就是$l=l_0+l_x$
详情请见注释,另外代码中虽然使用了快速读写,但输入规模还不足以使其产生巨大优势(带了573,不带591),不过对于担心i/o流同步关闭之后,C和C++风格的i/o混用之后出现问题的玩家们,这些给出了避开的方式
C++ 代码
#include <iostream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
using namespace std;
const int N = 3e4 + 7;
//快速读写,都将字符流拆分为一个个单字符,一定程度上可以提速
//不一定要封装在命名空间,封装的目的只是体现整体性
namespace FastIO {
void quickRead(int& _Dest) {
_Dest = 0;
int sgn = 1;
char ch = cin.get();
while (ch < '0' || ch > '9') {
if (ch == '-') {
sgn = -1;
}
ch = cin.get();
}
while (ch >= '0' && ch <= '9') {
_Dest = 10 * _Dest + (int)(ch - '0');
ch = cin.get();
}
_Dest *= sgn;
}
void quickWrite(int _Src) {
if (_Src < 0) {
cout.put('-');
_Src *= -1;
}
if (_Src >= 10) quickWrite(_Src / 10);
cout.put(_Src % 10 + '0');
return;
}
}
/*
* ori[i]是战舰i所在列的排头,刚开始都是自身
* len[i]是战舰i所在列的长度
* toHead[i]是战舰i和对应排头之间的间隔数
*/
int ori[N], len[N], toHead[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//并查集的基本初始化方式
iota(ori, ori + N, 0);
fill(len, len + N, 1);
int t;
FastIO::quickRead(t);
//方括号里边只要有引用传递的&就能实现递归,不用把函数对象名再写一遍,否则无法访问局部变量
function<int(int)> find = [&](int x)->int {
if (x != ori[x]) {
int origin = find(ori[x]);
//路径压缩的时候,间隔数是在压缩前的基础上累加的
toHead[x] += toHead[ori[x]];
ori[x] = origin;
}
return ori[x];
};
//合并两列为一列
auto mergeIntoOneColumn = [=](int x, int y) {
int src = find(x), dest = find(y);
if (src == dest) return;
//相似的,并为一列的时候,要在源队列的间隔数上累加目标队列的长度
//因为这个时候源队列已经视作在目标队列后面了
toHead[src] += len[dest];
ori[src] = dest;
//合并完成之后,目标队列的长度要加上源队列的长度
len[dest] += len[src];
};
//统计同列两战舰之间的战舰数(不同列返回-1)
auto cntBetweenTwoShips = [=](int x, int y)->int {
int pr = find(x), nx = find(y);
if (pr != nx) return -1;
//两战舰之间的战舰数等于间隔数-1,间隔数为0和1的时候都应该返回0
else return max(abs(toHead[x] - toHead[y]) - 1, 0);
};
while (t--) {
char op = cin.get();
int x, y;
FastIO::quickRead(x);
FastIO::quickRead(y);
if (op == 'M') mergeIntoOneColumn(x, y);
else {
FastIO::quickWrite(cntBetweenTwoShips(x, y));
cout.put('\n');
}
}
return 0;
}