题意:
初始化有$n$艘战舰分别在$n$列上行驶,现在有$m$个操作。
操作有两种类型:
$M\ i\ j$ 表示将第$i$列上的所有战舰接到第$j$列的最后一个战舰的末尾
$C\ i\ j$ 表示查询编号为$i$和编号为$j$的战舰之间的距离,如果它们不在一列上,则返回$-1$
数据范围:$1\leq n\leq 30000, 1\leq m\leq 500000$
题解:
首先本题需要考虑合并的问题,将第$i$列的战舰接到第$j$列战舰后时,那么就可以查询更多的战舰之间的距离。
考虑如何维护这些距离使得查询时更快,则每次更新第$i$列战舰接到第$j$列战舰后时,更新其中的所有战舰到
第$j$列根战舰的距离。
暴力更新每个第$i$列战舰到第$j$列根战舰的距离的时间复杂度:$O(n)$,更新距离的总时间复杂度就是:$O(n^2)$
所以需要考虑优化更新方式:$siz[i]$记录第$i$列的战舰数,$d[i]$表示编号为$i$的战舰到其当前所在列的根战舰的距离。
每次合并时,只需要更新$i$列根战舰到$j$列根战舰的距离
d[p[i]] = siz[p[j]];
siz[p[j]] += siz[p[i]];
p[p[i]] = p[j];
至于每个具体战舰,只需要在查询时更新其根结点时顺便更新即可。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 30010;
int p[N], n, m;
int siz[N], d[N];
char op[2];
int x, y;
int find(int x) {
if(x != p[x]) {
int rt = find(p[x]);
d[x] += d[p[x]];
p[x] = rt;
}
return p[x];
}
int main()
{
for(int i = 0; i < N; ++i) p[i] = i, siz[i] = 1, d[i] = 0;
scanf("%d", &m);
while(m--) {
scanf("%s%d%d", op, &x, &y);
int px = find(x), py = find(y);
if(*op == 'M') {
d[px] = siz[py];
siz[py] += siz[px];
p[px] = py;
}
else {
if(px != py) puts("-1");
else printf("%d\n", max(0, abs(d[x] - d[y]) - 1));
}
}
return 0;
}