两个区间只要交集长度大于零就能互相走到,于是可达即无向连通:并查集维护连通块,再用按左端点有序的表把每个连通块压成一段线段并在线合并。
OJ: roj
题目 ID: 1753
难度:提高+/省选-
标签:并查集数据结构区间合并python
创建: 2026-10-07 21:46
更新: 2026-10-07 21:46
形式化题目
依次处理
1 x y:把区间加入集合,成为第 个区间;保证它的长度严格大于此前所有区间的长度。 2 a b:询问是否存在一条从第个区间走到第 个区间的路径。
其中"从
即 YES / NO。端点都在 32 位有符号整数范围内,
正解
思路
第一步:把"能走一步"翻译成区间相交。 条件
| 位置关系 | 结论 | |
|---|---|---|
| 交错( |
成立( |
能走 |
| 成立( |
能走 | |
| 端点相切( |
不成立 | 不能走 |
| 完全分离 | 不成立 | 不能走 |
只要两个区间的交集长度大于零,就至少有一方的端点落在对方内部,因此这两个区间
能互相走到;反之,若交集为空或只共用一个端点(相切),则一个端点都落不进去。
样例里 NO,正是"相切不算连通"的印证。
所以本题的可达关系就是普通的无向连通,问题变成:动态往图里加边,询问两点是否连通。
第二步:并查集 + 把连通块压成线段。 加边与询问连通性用并查集即可,
瓶颈在于"加入新区间时该和哪些旧区间合并"——枚举全部旧区间是
关键观察:同一个连通块内所有区间的并集是一段连续线段,中间不会有空隙。
理由是若两个区间的并集留下空隙,这两个区间之间就不存在相交链把它们连起来,
它们本就不该在同一个连通块里。于是每个连通块都可以用一段
第三步:一次插入吸收一段连续线段。 新加入
- 先定位起点。取左端点
的最后一条线段(即有序表里最后一个 ): 若它的右端点 ,说明它跨过 ,与 相交,从它开始; 否则从第一条 的线段开始。 - 从起点往后扫,只要
就吸收:新线段取并集 , 并把该线段所在的连通块与新区间合并;被吸收的线段从有序表里删除。 - 起点之后所有
的线段必然满足 ,所以" "这个条件不用再判。
吸收结束后把并出来的线段
以样例为例(端点相切不计入):
| 操作 | 有序表(线段 |
说明 |
|---|---|---|
1 1 5 |
第一个连通块 | |
1 5 11 |
||
2 1 2 |
— | 两个块,输出 NO |
1 2 9 |
跨过 |
|
2 1 2 |
— | 同块,输出 YES |
代码
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 21:46
* update_at: 2026-10-07 21:46
*/
// 1753 区间连通性
// 两个区间只要交集长度 > 0 就能互相走到(端点相切不算),所以"可达"就是普通的
// 无向连通:并查集维护连通块;同一连通块内所有区间的并集恰好是一段连续线段,
// 于是用一个按左端点排序的 map 维护"各连通块的线段",插入新区间时把与之
// 正长度相交的线段全部并进来(每条线段只会被删一次)。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
typedef long long ll;
int n;
int fa[MAXN]; // 并查集父指针
int siz[MAXN]; // 并查集块大小
// 连通块线段:左端点 -> (右端点, 该连通块的并查集代表元)
map<ll, pair<ll, int> > seg;
// 找 x 所在连通块的代表元,顺路做路径减半。
int find_root(int x) {
while (fa[x] != x) {
fa[x] = fa[fa[x]];
x = fa[x];
}
return x;
}
// 合并两个区间所在的连通块(按大小合并)。
void merge_block(int a, int b) {
a = find_root(a);
b = find_root(b);
if (a == b) return;
if (siz[a] < siz[b]) swap(a, b);
fa[b] = a;
siz[a] += siz[b];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
fa[i] = i;
siz[i] = 1;
}
int cnt = 0; // 已经加入的区间个数,也就是区间编号
for (int i = 1; i <= n; i++) {
int op;
cin >> op;
if (op == 1) {
ll x, y;
cin >> x >> y;
cnt++;
// 找第一个可能与 (x,y) 正长度相交的线段:
// 左端点 <= x 的那条线段若右端点 > x,说明它跨过 x,从它开始;
// 否则从第一条左端点 > x 的线段开始。
map<ll, pair<ll, int> >::iterator it = seg.upper_bound(x);
if (it != seg.begin()) {
map<ll, pair<ll, int> >::iterator pre = prev(it);
if (pre->second.first > x) it = pre;
}
// 线段两两不相交,所以从这里开始,凡左端点 < y 的线段都跨过 x,逐条吸收
ll nl = x;
ll nr = y;
while (it != seg.end() && it->first < y) {
nl = min(nl, it->first);
nr = max(nr, it->second.first);
merge_block(cnt, it->second.second);
it = seg.erase(it);
}
seg[nl] = make_pair(nr, find_root(cnt));
} else {
int a, b;
cin >> a >> b;
cout << (find_root(a) == find_root(b) ? "YES" : "NO") << '\n';
}
}
return 0;
}#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 22:29
# update_at: 2026-10-07 22:29
import sys
from bisect import bisect_right
type SegMap = dict[int, tuple[int, int]] # 线段表:左端点 -> (右端点, 所在连通块的并查集代表元)
# 每个连通块内所有区间的并集是一段连续线段,线段表就是这些线段本身:
# LEFTS 是存活线段的左端点升序表(唯一需要查找的结构)
# SEG 是同一批线段的详情表,两张表用左端点对齐
# PARENT / SIZE 是并查集,下标是区间编号
LEFTS: list[int] = []
SEG: SegMap = {}
PARENT: list[int] = []
SIZE: list[int] = []
def find(x: int) -> int:
"""区间编号 x 所在连通块的代表元(路径减半)。"""
while PARENT[x] != x:
PARENT[x] = PARENT[PARENT[x]]
x = PARENT[x]
return x
def union(a: int, b: int) -> None:
"""把两个区间所在的连通块合并成一个(按大小合并)。"""
a, b = find(a), find(b)
if a == b:
return
if SIZE[a] < SIZE[b]:
a, b = b, a
PARENT[b] = a
SIZE[a] += SIZE[b]
def absorb(x: int, y: int, cnt: int) -> None:
"""把区间 (x,y)(编号 cnt)并进线段表:吸收所有与它正长度相交的线段。"""
# 起点:跨过 x 的那条线段(左端点 <= x 且右端点 > x),否则第一条左端点 > x 的线段
i = bisect_right(LEFTS, x)
start = i - 1 if i > 0 and SEG[LEFTS[i - 1]][0] > x else i
# 线段两两不相交,所以从起点起凡左端点 < y 的线段都跨过 x,逐条吸收
nl, nr = x, y
j = start
while j < len(LEFTS) and LEFTS[j] < y:
l = LEFTS[j]
nl = min(nl, l)
nr = max(nr, SEG[l][0])
union(cnt, SEG[l][1])
j += 1
for l in LEFTS[start:j]:
del SEG[l]
LEFTS[start:j] = [nl] # 被吸收的线段整段换成本次并出来的线段
SEG[nl] = (nr, find(cnt))
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
PARENT.extend(range(n + 1))
SIZE.extend([1] * (n + 1))
cnt = 0 # 已加入的区间个数,也就是区间编号
out: list[str] = []
for _ in range(n):
op, x, y = next(data), next(data), next(data)
if op == 2:
same_block = find(x) == find(y) # 两个区间是否落在同一个连通块
out.append("YES" if same_block else "NO")
continue
cnt += 1
absorb(x, y, cnt)
sys.stdout.write("\n".join(out) + "\n")
if __name__ == "__main__":
solve()Python 没有平衡树,main.py 用 bisect 维护存活线段的左端点有序表:
查找
复杂度
- 时间复杂度:
。每个区间(线段)只被插入一次、删除一次, 有序表操作 ,并查集近似常数。 - 空间复杂度:
,存并查集、有序表与每个线段的右端点、所属连通块。
总结
- 题面给的单步条件看似有方向,落到区间位置上其实就是"交集长度大于零", 于是可达性是无向连通,可以直接用并查集维护。
- 动态加边时不要枚举旧区间:一个连通块内的区间并集是一段连续线段,
按左端点排序后,一次插入吸收的线段在表里是连续一段,每条线段只被删一次,
从而做到
。 - 端点相切(
恰好等于 ,或 恰好等于 )不算相交,代码里用的是严格不等号。
来源与数据说明:本题出自信息学奥赛一本通·高手训练篇(数据结构)第 1753 题, 本仓库的题面为网络重建,数据由同目录
data.py用自带标程现场生成,并非官方数据。 另外题面把单步条件写成有方向的或 :若严格按有向图理解, “外层区间走不到被它包含的内层区间”,答案会与"交集非空"的无向读法不同 (例如 时,无向读法三者同块, 有向读法则 走不到 )。本题按题名"连通性"取无向语义, 与仓库数据的判定一致;若评测方采用有向语义,则需另做处理。 题面中"新加入的区间长度严格大于此前所有区间"这一保证对无向建模并不需要, 它只是让数据更有结构。