CF1029C
[TOC]
题意
给你n个线段,给出其左右端点,求去掉其中一个边,剩下的线段的最大交集
输入
第一行给出一个n(2<=n<=3e5)
接下来N行,每一行给出l,r(0<=l<=r<=1e9)
输出
输出n-1条边的最大交集.
解析
看到这个题我想起了之前做过的一个题(CF1132C),博客链接
当时那个题是枚举去掉的两条边,然后前缀和求解的,但是我发现这个题的l,r范围过大,数组开不下,所以此题绝对不能前缀和求区间之类的操作了,但是线段数量不大,应该是可以枚举的,问题就在于去掉某个边,怎么求解剩余的边的交集
我们发现,所谓交集一定是由某个线段的左端点发出,一直到某个线段的右端点停止.
所以我们构建两个数组(为了方便我们这里采用了优先队列),分别维护所有左端点和右端点,然后在去除某边的时候判断一下其是否会对左端点的最大值和右端点的最小值构成影响,我们此处可以判断其某个端点就是当前并集的边界的话,我们对那个队列进行pop操作,然后重新并集,并与并集最大值比较,进行更新,然后我们再将此线段加回去
代码
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
// AC 考察优先队列用法,当然此题也可以使用mulset来解决,总之是用二叉树求最值的性质
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <string>
#include <set>
#include <queue>
using namespace std;
struct seg {
int l, r;
};
seg Seg[300000];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
priority_queue<int, vector<int>, less<int> > L;
priority_queue<int, vector<int>, greater<int> > R;
for (int i = 0; i < n; ++i) {
cin >> Seg[i].l >> Seg[i].r;
L.push(Seg[i].l); // 分别维护其左右端点
R.push(Seg[i].r);
}
int manx = 0; // 考虑到并集可能为0
for (int i = 0; i < n; ++i) {
bool left = 0, right = 0;
if (Seg[i].l == L.top()) { // 当前线段线段的左端点就是并集左端点,然后pop,左队列的队首就变成了去掉这个线段后最大的左端点
left = 1;
L.pop();
}
if (Seg[i].r == R.top()) { // 同左端点
right = 1;
R.pop();
}
manx = max(manx, R.top() - L.top());
if (left) {
L.push(Seg[i].l);
}
if (right) {
R.push(Seg[i].r);
}
}
cout << manx << endl;
return 0;
}
启示
这个维护方式我觉得很简单而巧妙,还是看数据范围是允许枚举操作的,整体复杂度O(n*logn),还是很优雅的.
