UVa 12647 Balloon

题目描述

给定一个由若干线段组成的天花板，线段之间没有公共点。气球从地面点 $(x,0)$ 垂直向上释放。当气球碰到水平线段时，它会卡在该位置；当碰到倾斜线段时，它会沿着线段滑到该线段的最高点，然后从该点继续垂直向上运动。这个过程可能重复多次，最终气球要么卡在某条水平线段上，要么从大厅逃出。

需要回答多个查询，每个查询给定一个释放点的横坐标 $x$，输出气球的最终位置：若逃出则输出逃出时的横坐标，否则输出卡住位置的坐标 $(x,y)$。

输入格式

每个测试用例第一行包含两个整数 $N$ 和 $C$，分别表示线段数量和查询数量。

接下来 $N$ 行，每行四个整数 $X_1,Y_1,X_2,Y_2$，描述一条线段的两个端点。

接下来 $C$ 行，每行一个整数 $X$，表示查询的释放点横坐标。

输入包含多个测试用例，直到文件结束。

输出格式

对于每个查询，输出一行：

• 若气球逃出，输出一个整数 $X$，表示逃出时的横坐标。
• 否则输出两个整数 $X$ 和 $Y$，表示卡住的位置。

样例

输入

4 4
0 1 3 3
1 5 6 5
5 3 2 4
7 4 10 2
2
5
8
6
4 3
1 3 4 2
10 3 7 4
2 3 8 3
3 5 5 4
4
9
8

输出

2 5
2 5
7
6 5
1
7
8 3

题目分析

本题的核心是模拟气球在天花板下的运动轨迹。天花板由若干线段组成，线段之间没有公共点，且所有端点的横坐标互不相同。

直接模拟的方法是从释放点开始，每次找到当前正上方最近的线段。如果是水平线段，气球卡住；如果是倾斜线段，气球滑到最高点后继续向上。这个过程可能重复多次。

然而，直接模拟存在两个问题：

• 每次查找上方最近线段需要遍历所有线段，复杂度 $O(N)$。
• 每个查询可能经历多次滑动，最坏情况下每个查询需要 $O(N)$ 次查找。

总的复杂度为 $O(C\cdot N^2)$，在 $N,C\le 10^5$ 时不可接受。

解题思路

核心洞察

从高到低处理线段 是本题的关键。

假设我们按照线段的高度从高到低处理。当处理到一条倾斜线段时，它最高点正上方的线段一定已经被处理过了（因为更高）。因此，这条倾斜线段可以直接“继承”其最高点正上方线段的结果，而不需要模拟气球在它上方的多次滑动。

这个思路将问题转化为：用线段树维护每个横坐标当前被哪条线段覆盖，从高到低处理每条线段，并记录每条线段最终会卡在哪条水平线段上。

预处理

首先，对每条线段进行处理，保证其左端点的纵坐标不小于右端点的纵坐标：

if (seg[i].y1 < seg[i].y2) {
swap(seg[i].x1, seg[i].x2);
swap(seg[i].y1, seg[i].y2);
}

这样处理后：

• 水平线段：$y_1=y_2$
• 倾斜线段：最高点一定在 $(x_1,y_1)$

同时，添加一条无限高的水平线段作为“天花板”，其高度为 $MAXC+1$，其中 $MAXC=1000010$ 是横坐标的最大范围。这样，所有查询的最终归宿要么是某条真实的水平线段，要么是这条天花板（表示逃出）。

数据结构

使用线段树维护区间覆盖：

• cover[rt] 表示当前节点对应的区间被哪条线段覆盖，$-1$ 表示未被覆盖。
• 支持区间赋值操作（update）和单点查询操作（query）。

算法流程

正确性说明

由于我们按照高度从高到低处理，当处理到一条倾斜线段时，它最高点上方的线段已经处理完毕，因此其最终归宿可以直接继承。这与气球实际运动的逻辑一致：气球从低处向上运动，最终卡住的水平线段由最上方的那条决定。

线段树维护了每个横坐标当前被哪条线段覆盖，保证了查询和继承操作的正确性。

复杂度分析

• 排序：$O(N\log N)$
• 线段树操作：每次更新和查询均为 $O(\log MAXC)$，共 $O(N+C)$ 次操作
• 总时间复杂度：$O((N+C)\log MAXC)$，其中 $MAXC=1000010$ 为常数
• 空间复杂度：$O(MAXC)$

代码实现

// Balloon
// UVa ID: 12647
// Verdict: Accepted
// Submission Date: 2026-06-12
// UVa Run Time: 0.120s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

const int MAXC = 1000010;
const int MAXN = 100010;

int cover[MAXC << 2];
int f[MAXN];
int ansX[MAXN];
int n, m;

struct Segment {
int x1, y1, x2, y2;
bool operator<(const Segment &b) const {
return y1 < b.y1;
}
} seg[MAXN];

void pushDown(int rt) {
if (cover[rt] != –1) {
cover[rt << 1] = cover[rt << 1 | 1] = cover[rt];
cover[rt] = –1;
}
}

void update(int L, int R, int idx, int l, int r, int rt) {
if (L <= l && r <= R) {
cover[rt] = idx;
return;
}
int m = (l + r) >> 1;
pushDown(rt);
if (L <= m) update(L, R, idx, l, m, rt << 1);
if (R > m) update(L, R, idx, m + 1, r, rt << 1 | 1);
}

int query(int x, int l, int r, int rt) {
if (cover[rt] >= 0) return cover[rt];
int m = (l + r) >> 1;
if (x <= m) return query(x, l, m, rt << 1);
else return query(x, m + 1, r, rt << 1 | 1);
}

void solve() {
sort(seg, seg + n + 1);
memset(cover, –1, sizeof(cover));
for (int i = n; i >= 0; —i) {
if (seg[i].y1 == seg[i].y2) {
f[i] = i;
} else {
int k = query(seg[i].x1, 0, MAXC, 1);
f[i] = f[k];
if (seg[k].y1 == seg[k].y2) ansX[i] = seg[i].x1;
else ansX[i] = ansX[k];
}
int L = seg[i].x1, R = seg[i].x2;
if (L > R) swap(L, R);
update(L, R, i, 0, MAXC, 1);
}
}

void answerQuery(int x) {
int k = query(x, 0, MAXC, 1);
if (seg[k].y1 != seg[k].y2) x = ansX[k];
if (f[k] == n) cout << x << '\\n';
else cout << x << ' ' << seg[f[k]].y1 << '\\n';
}

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

while (cin >> n >> m) {
for (int i = 0; i < n; ++i) {
cin >> seg[i].x1 >> seg[i].y1 >> seg[i].x2 >> seg[i].y2;
if (seg[i].y1 < seg[i].y2) {
swap(seg[i].x1, seg[i].x2);
swap(seg[i].y1, seg[i].y2);
}
}
seg[n].x1 = 0;
seg[n].y1 = MAXC + 1;
seg[n].x2 = MAXC;
seg[n].y2 = MAXC + 1;
solve();
while (m—) {
int x;
cin >> x;
answerQuery(x);
}
}
return 0;
}

总结

本题的核心技巧是逆向思维和区间覆盖：

这种方法将复杂的问题转化为经典的线段树区间覆盖问题，时间复杂度 $O((N+C)\log MAXC)$，足以通过 $N,C\le 10^5$ 的数据规模。类似的思路可应用于其他涉及“向上碰撞”或“依赖关系”的问题中。