这道题目是一道经典的区间染色问题。虽然数轴范围高达 \(10^9\)，但由于染色操作次数 \(N\) 较小（最大 5000），我们可以通过坐标离散化或动态维护区间的方法来解决。
解题思路
-
离散化 (Discretization)：
数轴范围巨大，但 \(N\) 次操作涉及的端点最多只有 \(2N = 10,000\) 个。我们将所有涉及到的 \(a_i\) 和 \(b_i\) 收集起来，从小到大排序并去重，形成一系列相互连接的小区间。
-
区间状态维护：
离散化后，原本连续的数轴被切成了若干个“原子区间”。我们可以用一个数组来记录每个区间的颜色。
-
模拟染色：
遍历每一次输入，将对应范围内的“原子区间”标记为白色或黑色。
-
合并与统计：
染色结束后，遍历所有区间，将连续的白色区间合并，记录长度最大且起始点最小的那一段。
C++ 实现代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>using namespace std;struct Query {int l, r;char color;
};int main() {int N;if (!(cin >> N)) return 0;vector<Query> ops(N);vector<int> coords;// 初始区间端点，题目范围是 0 到 10^9coords.push_back(0);coords.push_back(1000000000);for (int i = 0; i < N; ++i) {cin >> ops[i].l >> ops[i].r >> ops[i].color;coords.push_back(ops[i].l);coords.push_back(ops[i].r);}// 1. 离散化：排序并去重sort(coords.begin(), coords.end());coords.erase(unique(coords.begin(), coords.end()), coords.end());// 2. 初始化颜色：0表示黑色，1表示白色。初始全为白色。// 离散化后 m 个点产生 m-1 个区间int m = coords.size();vector<int> color(m, 1);// 3. 模拟染色过程for (int i = 0; i < N; ++i) {// 找到当前操作在离散化数组中的下标int L = lower_bound(coords.begin(), coords.end(), ops[i].l) - coords.begin();int R = lower_bound(coords.begin(), coords.end(), ops[i].r) - coords.begin();int c = (ops[i].color == 'w' ? 1 : 0);for (int j = L; j < R; ++j) {color[j] = c;}}// 4. 统计最长白色段int max_len = -1;int ans_l = 0, ans_r = 0;int cur_l = -1;for (int i = 0; i < m; ++i) {if (i < m - 1 && color[i] == 1) {if (cur_l == -1) cur_l = coords[i]; // 记录段起点} else {if (cur_l != -1) {int cur_r = coords[i]; // 记录段终点int len = cur_r - cur_l;if (len > max_len) {max_len = len;ans_l = cur_l;ans_r = cur_r;}cur_l = -1;}}}if (max_len == -1) return 0;cout << ans_l << " " << ans_r << endl;return 0;
}
关键点拨
-
离散化原理：
假设有两个操作 \([10, 20]\) 和 \([15, 30]\)。端点集合为 \(\{10, 15, 20, 30\}\)。这会产生三个区间：\([10, 15]\)、\([15, 20]\) 和 \([20, 30]\)。通过操作下标，我们可以精准地控制这些小区间的状态。
-
复杂度分析：
- 排序与去重：\(O(N \log N)\)
- 染色操作：\(O(N^2)\)（最坏情况下每次都要遍历所有原子区间）
- 鉴于 \(N=5000\)，\(N^2\) 约为 \(2.5 \times 10^7\)，在 1 秒的限时内完全可以跑通。
-
边界处理：
注意题目中数轴范围到 \(10^9\)，但在初始时全为白色，因此默认把 \(0\) 和 \(10^9\) 加入坐标集合。