区间连通性

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

两个区间只要交集长度大于零就能互相走到,于是可达即无向连通:并查集维护连通块,再用按左端点有序的表把每个连通块压成一段线段并在线合并。

OJ: roj

题目 ID: 1753

难度:提高+/省选-

标签:并查集数据结构区间合并python

创建: 2026-10-07 21:46

更新: 2026-10-07 21:46

形式化题目

依次处理 nn 个操作,维护一个动态加入的开区间集合。加入的第 kk 个区间记为 Ik=(xk,yk)I_k = (x_k, y_k),编号从 11 开始。

  • 1 x y:把区间 (x,y)(x,y) 加入集合,成为第 kk 个区间;保证它的长度严格大于此前所有区间的长度。
  • 2 a b:询问是否存在一条从第 aa 个区间走到第 bb 个区间的路径。

其中"从 (a,b)(a,b) 走到 (c,d)(c,d)"的含义是

c<a<d或c<b<d,c < a < d \quad \text{或} \quad c < b < d,

即 (a,b)(a,b) 的某个端点严格落在 (c,d)(c,d) 内部。路径由若干次这样的单步组成, 每个询问独立回答 YES / NO。端点都在 32 位有符号整数范围内,1⩽n⩽1051 \leqslant n \leqslant 10^5。

正解

思路

第一步:把"能走一步"翻译成区间相交。 条件 c<a<dc<a<d 或 c<b<dc<b<d 说的是 “(a,b)(a,b) 的端点在 (c,d)(c,d) 内部”。逐个检查两个区间的相对位置:

位置关系 c<a<dc<a<d 或 c<b<dc<b<d 结论
交错(a<c<b<da<c<b<d) 成立(bb 落在 (c,d)(c,d) 内) 能走
(a,b)⊂(c,d)(a,b) \subset (c,d) 成立(aa 落在 (c,d)(c,d) 内) 能走
端点相切(b=cb=c) 不成立 不能走
完全分离 不成立 不能走

只要两个区间的交集长度大于零,就至少有一方的端点落在对方内部,因此这两个区间 能互相走到;反之,若交集为空或只共用一个端点(相切),则一个端点都落不进去。 样例里 (1,5)(1,5) 与 (5,11)(5,11) 相切,第一问输出 NO,正是"相切不算连通"的印证。 所以本题的可达关系就是普通的无向连通,问题变成:动态往图里加边,询问两点是否连通。

第二步:并查集 + 把连通块压成线段。 加边与询问连通性用并查集即可, 瓶颈在于"加入新区间时该和哪些旧区间合并"——枚举全部旧区间是 O(n2)O(n^2)。

关键观察:同一个连通块内所有区间的并集是一段连续线段,中间不会有空隙。 理由是若两个区间的并集留下空隙,这两个区间之间就不存在相交链把它们连起来, 它们本就不该在同一个连通块里。于是每个连通块都可以用一段 [L,R][L,R] 完整表示, 所有线段按左端点 LL 排序维护在一张有序表里。

第三步:一次插入吸收一段连续线段。 新加入 (x,y)(x,y) 后,与它正长度相交的线段 恰好是满足 L<yL<y 且 R>xR>x 的那些。由于线段两两不相交且有序,这些线段在有序表里 是连续的一段:

  • 先定位起点。取左端点 ⩽x\leqslant x 的最后一条线段(即有序表里最后一个 L⩽xL \leqslant x): 若它的右端点 R>xR>x,说明它跨过 xx,与 (x,y)(x,y) 相交,从它开始; 否则从第一条 L>xL>x 的线段开始。
  • 从起点往后扫,只要 L<yL<y 就吸收:新线段取并集 [min⁡(L,x),max⁡(R,y)][\min(L,x),\max(R,y)], 并把该线段所在的连通块与新区间合并;被吸收的线段从有序表里删除。
  • 起点之后所有 L<yL<y 的线段必然满足 R>L>xR>L>x,所以"R>xR>x"这个条件不用再判。

吸收结束后把并出来的线段 [L′,R′][L',R'] 重新插入有序表。每条线段只被插入一次、 删除一次,因此总工作量是 O(nlog⁡n)O(n\log n);询问就是并查集上的一次查根。

以样例为例(端点相切不计入):

操作 有序表(线段 →\to 连通块) 说明
1 1 5 [1,5][1,5] 第一个连通块
1 5 11 [1,5][1,5],[5,11][5,11] 5<55<5 不成立,相切不合并
2 1 2 — 两个块,输出 NO
1 2 9 [1,11][1,11] 跨过 x=2x=2 的 [1,5][1,5] 与 L=5<9L=5<9 的 [5,11][5,11] 都被吸收
2 1 2 — 同块,输出 YES

代码

cpp
/**
 * 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;
}
python
#!/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 维护存活线段的左端点有序表: 查找 O(log⁡n)O(\log n),吸收时整段切片替换。算法与 C++ 完全同阶。

复杂度

  • 时间复杂度:O(nlog⁡n)O(n\log n)。每个区间(线段)只被插入一次、删除一次, 有序表操作 O(log⁡n)O(\log n),并查集近似常数。
  • 空间复杂度:O(n)O(n),存并查集、有序表与每个线段的右端点、所属连通块。

总结

  • 题面给的单步条件看似有方向,落到区间位置上其实就是"交集长度大于零", 于是可达性是无向连通,可以直接用并查集维护。
  • 动态加边时不要枚举旧区间:一个连通块内的区间并集是一段连续线段, 按左端点排序后,一次插入吸收的线段在表里是连续一段,每条线段只被删一次, 从而做到 O(nlog⁡n)O(n\log n)。
  • 端点相切(LL 恰好等于 yy,或 RR 恰好等于 xx)不算相交,代码里用的是严格不等号。

来源与数据说明:本题出自信息学奥赛一本通·高手训练篇(数据结构)第 1753 题, 本仓库的题面为网络重建,数据由同目录 data.py 用自带标程现场生成,并非官方数据。 另外题面把单步条件写成有方向的 c<a<dc<a<d 或 c<b<dc<b<d:若严格按有向图理解, “外层区间走不到被它包含的内层区间”,答案会与"交集非空"的无向读法不同 (例如 (40,60)⊂(10,90)⊂(0,100)(40,60) \subset (10,90) \subset (0,100) 时,无向读法三者同块, 有向读法则 (0,100)(0,100) 走不到 (40,60)(40,60))。本题按题名"连通性"取无向语义, 与仓库数据的判定一致;若评测方采用有向语义,则需另做处理。 题面中"新加入的区间长度严格大于此前所有区间"这一保证对无向建模并不需要, 它只是让数据更有结构。