CF1249D1
题意
给出一个x轴(可以假想x轴的范围是[1,2e5]),然后给出n,k.
接下来给出n个线段的l,r.添加到x轴上.
要求删除一些线段,使得在[1,2e5]范围内,任何一个点上覆盖的线段数量<=k.
第一行输出删除的条数,
第二行删除的每一条的编号(任意顺序).
$1<=k,n,l_i,r_i<=2e5$
思路
这个题一开始就确定了思路,就是利用差分(树状数组)先维护每个点上覆盖的线段数.
然后依次从左到右遍历所有的点,如果某个点的线段数超过K,那么就删除其上的右端点最远的线段(贪心思想,既然删除就尽量惠及尽可能多的后面的,由于前面的都已经安排好了,后面的删除不会影响前面的决策,所以只需要在乎右端点就可以了).删除操作可以像添加一样,区间修改就可以了.
正解的思路就是这样,但是怎么实现快速的找到右端点最远的线段呢?
我一开始想到了一个思路,但是操作较复杂.
是这样的,除了此树状数组之外,还维护一个线段树,这个线段树就是用来让区间变成定值(这个模板需要积极整理),然后插入线段的时候先进行排序,按照右端点排序,然后 每次插入之后就以右端点的坐标覆盖区间的值.然后就可以log的时间内找到单点的最远右端点了.
这个思路是对的,但是这个实现的复杂度稍复杂.
看了看大佬的代码,发现了很简单的做法.
我们将所有线段挂在其左端点上,然后用一个set表示当前已经加入到数轴的线段.(实际上一个线段有三个参数,左端点,右端点和标号)
从左到右遍历数组,然后将所有挂在当前坐标的线段都加入set,然后利用树状数组区间更新(就是加入线段了),然后查询当前节点的线段数(单点查询),如果大于k,然后删掉set中右端点最大的,同时记录下删除的线段的下标.
最后输出答案即可.
这个问题的关键和上文一样,就是如何删除最远的节点.其实可以将线段的结构体的优先级设置为右端点越大,优先级越低,然后删除最后的即可.还是很巧妙的,需要仔细学一下set的用法.
AC代码
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 200000 + 100
struct seg {
int l, r;
} s[maxn];
int k, n; // m;
int a[500000 + 100], P[500000 + 100];
int lowbit(int x) {
return x & (-x);
}
void add(int x, int y) {
while (x <= n) {
P[x] += y;
x += lowbit(x);
}
}
ll qzsum(int x) {
ll ans = 0ll;
while (x > 0) {
ans += P[x];
x -= lowbit(x);
}
return ans;
}
vector<pair<int, int> > v[maxn];
set<pair<int, int> > seg;
int main() {
int n1;
cin >> n1 >> k;
for (int i = 1; i <= n1; ++i) {
int l, r;
cin >> l >> r;
v[l].push_back(make_pair(r, i)); // 挂在左端点
}
vector<int> ans;
n = maxn;
for (int i = 1; i <= (int)(2e5); ++i) {
int len = v[i].size();
for (int j = 0; j < len; ++j) {
add(i, 1);
add(v[i][j].first + 1, -1);
seg.insert(v[i][j]);
}
while (qzsum(i) > k) {
// 神奇的使用方法
int R = seg.rbegin()->first;
int id = seg.rbegin()->second;
seg.erase(seg.lower_bound({R, id}));
add(i, -1);
add(R + 1, 1);
ans.push_back(id);
}
}
int len = ans.size();
printf("%d\n", len);
for (int i = 0; i < len; ++i) {
if (i != 0) {
printf(" ");
}
printf("%d", ans[i]);
}
printf("\n");
return 0;
}
