[NOI2002] 银河英雄传说

GitHub 跳转原题关系图返回列表

把每一列看成一个并查集集合，维护每艘战舰到队头的距离；合并时整体挂到另一列后面，就能在线回答两舰之间隔了多少艘船。

OJ: luogu

题目 ID: P1196

难度:提高+/省选-

标签:并查集带权并查集合

日期: 2026-06-20 00:22

相似题目

luogu P5937[CEOI 1999] Parity Game把父子关系权值从 XOR 换成普通加法，练习距离型位势并查集。

题意

一开始 1..30000 号战舰各自单独成列。

操作 M i j 表示：把 i 所在整列，按原顺序接到 j 所在整列的尾部。

操作 C i j 表示：如果 i 和 j 当前不在同一列，输出 -1；否则输出它们之间隔着多少艘战舰。

样例里的两次合并，可以只看相关的 4 艘战舰：

时刻	队列状态
初始	`[1] [2] [3] [4]`
`M 2 3` 后	`[1] [3, 2] [4]`
`M 2 4` 后	`[1] [4, 3, 2]`

所以最后询问 C 4 2 时，4 和 2 中间只有 3，答案是 1。

思路

先看一个直接模拟小数据的暴力：

cpp

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// brute.cpp：直接按队列顺序模拟，只适合小数据理解和对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30005;

int q;
int belong[MAXN];
vector<int> ships[MAXN];

void init_queues() {
    for (int i = 1; i <= 30000; i++) {
        ships[i].clear();
        ships[i].push_back(i);
        belong[i] = i;
    }
}

void merge_queue(int x, int y) {
    int bx = belong[x];
    int by = belong[y];

    if (bx == by) {
        return;
    }

    for (int ship : ships[bx]) {
        ships[by].push_back(ship);
        belong[ship] = by;
    }
    ships[bx].clear();
}

int query_between(int x, int y) {
    int bx = belong[x];
    int by = belong[y];

    if (bx != by) {
        return -1;
    }
    if (x == y) {
        return 0;
    }

    int px = -1;
    int py = -1;
    for (int i = 0; i < (int)ships[bx].size(); i++) {
        if (ships[bx][i] == x) {
            px = i;
        }
        if (ships[bx][i] == y) {
            py = i;
        }
    }

    if (px > py) {
        swap(px, py);
    }
    return py - px - 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> q;
    init_queues();

    while (q--) {
        char op;
        int x, y;
        cin >> op >> x >> y;

        if (op == 'M') {
            merge_queue(x, y);
        } else {
            cout << query_between(x, y) << '\n';
        }
    }

    return 0;
}

暴力把每一列真的存成一个数组：

合并时，把一整列逐个搬到另一列末尾
查询时，在这一列里找出两个编号的位置

这个做法很好理解，但大数据下太慢，因为一次合并就可能搬很多战舰。

这题的关键是：整列合并时，一列内部的相对顺序完全不变，只是整体往后平移了一段距离。

所以可以用带权并查集维护三件事：

fa[x]：x 的父节点
sz[x]：当 x 是根时，这一列一共有多少艘战舰
dist_to_head[x]：x 前面有多少艘战舰

这里把并查集的根看成这一列的队头。

如果把 x 所在整列接到 y 所在整列后面，设两个队头分别是 rx 和 ry，那么：

新队头仍然是 ry
rx 整列会整体后移 sz[ry] 个位置
所以令 fa[rx] = ry，并设 dist_to_head[rx] = sz[ry]
再更新新队列长度 sz[ry] += sz[rx]

路径压缩时也要顺便把距离累加上去：

如果 x -> fa[x] -> root
那么压缩后 dist_to_head[x] += dist_to_head[old_fa]

这样，查询同一列的两艘战舰时：

abs(dist_to_head[x] - dist_to_head[y]) 是它们位置差
再减去两端自己，答案就是 abs(...) - 1

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30005;

int q;
int fa[MAXN], sz[MAXN], dist_to_head[MAXN];

void init_dsu() {
    for (int i = 1; i <= 30000; i++) {
        fa[i] = i;
        sz[i] = 1;
        dist_to_head[i] = 0;
    }
}

int find_root(int x) {
    if (fa[x] == x) {
        return x;
    }
    int old_fa = fa[x];
    fa[x] = find_root(fa[x]);
    dist_to_head[x] += dist_to_head[old_fa];
    return fa[x];
}

// 把 x 所在整列接到 y 所在整列的尾部。
void merge_queue(int x, int y) {
    int rx = find_root(x);
    int ry = find_root(y);

    if (rx == ry) {
        return;
    }

    // 并查集的根表示这一列的队头。
    // x 这一列整体接到 y 这一列后面，所以 x 这一列的队头
    // 前面会多出 sz[ry] 艘战舰。
    fa[rx] = ry;
    dist_to_head[rx] = sz[ry];
    sz[ry] += sz[rx];
}

int query_between(int x, int y) {
    int rx = find_root(x);
    int ry = find_root(y);

    if (rx != ry) {
        return -1;
    }
    if (x == y) {
        return 0;
    }

    return abs(dist_to_head[x] - dist_to_head[y]) - 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> q;
    init_dsu();

    while (q--) {
        char op;
        int x, y;
        cin >> op >> x >> y;

        if (op == 'M') {
            merge_queue(x, y);
        } else {
            cout << query_between(x, y) << '\n';
        }
    }

    return 0;
}

复杂度

设总操作数为 q。

并查集每次 find 和合并的均摊复杂度都近似常数，所以总时间复杂度是：

$O(q \alpha(30000))$

空间复杂度 $O(30000)$ 。

总结

这题不是普通并查集，而是“并查集 + 相对位置维护”。

真正要抓住的是那个不变量：dist_to_head[x] 始终表示 x 前面有多少艘战舰。只要这个量在合并和路径压缩后都保持正确，查询答案就只是一个位置差。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P1196 [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$ 行，每行有一条指令。指令有两种格式：

M i j： $i$ 和 $j$ 是两个整数（ $1 \le i,j \le 30000$ ），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第 $i$ 号战舰与第 $j$ 号战舰不在同一列。
C i j： $i$ 和 $j$ 是两个整数（ $1 \le i,j \le 30000$ ），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。

每条指令中都保证 $i\neq j$ 。

输出格式

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

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

输入输出样例 #1

输入 #1

text

输出 #1

text

1
2-1
1

说明/提示

样例解释

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

[NOI2002] 银河英雄传说

目录

题意

思路

代码

复杂度

总结

一图流解析