题解 CF1462F 【The Treasure of The Segments】
Warriors_Cat
2020-12-16 17:30:55
[题面传送门](https://www.luogu.com.cn/problem/CF1462F)
题意可以从这里看，这里不在赘述。
---
### $Solution:$
枚举那个要与所有线段相交的线段，统计需要删掉的线段个数即可。
很显然当一个线段的右端点小于这条线段的左端点，或者一个线段的左端点大于这条线段的右端点时，这个线段需要删除。
所以可以先统计每个点存在的端点个数，再用前缀和优化一下就行了。
注意到 $l, r \le 10^9$，于是需要离散化。
over，时间复杂度为 $O(n \log n)$。
### $Code:$
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <map>
using namespace std;
#define ll long long
#define fi first
#define se second
#define y1 y_csyakioi_1
#define y0 y_csyakioi_0
#define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 200010;
int t, n, lsh[N << 1], len, cl[N << 1], cr[N << 1];
struct node{
int l, r;
}a[N];
inline int id(int x){ return lower_bound(lsh + 1, lsh + len + 1, x) - lsh; }
inline void work(){
n = read(); len = 0;
for(int i = 1; i <= n; ++i) a[i].l = read(), a[i].r = read();
for(int i = 1; i <= n; ++i) lsh[2 * i - 1] = a[i].l, lsh[2 * i] = a[i].r;
sort(lsh + 1, lsh + 2 * n + 1);
len = unique(lsh + 1, lsh + 2 * n + 1) - lsh - 1;
for(int i = 1; i <= n; ++i) a[i].l = id(a[i].l), a[i].r = id(a[i].r);
for(int i = 1; i <= 2 * n; ++i) cl[i] = cr[i] = 0;
for(int i = 1; i <= n; ++i) ++cl[a[i].l], ++cr[a[i].r];
for(int i = 1; i <= 2 * n; ++i) cl[i] += cl[i - 1], cr[i] += cr[i - 1];
int ans = 0x7f7f7f7f;
for(int i = 1; i <= n; ++i){
ans = min(ans, cr[a[i].l - 1] + cl[2 * n] - cl[a[i].r]);
}
printf("%d\n", ans);
}
int main(){
t = read(); while(t--) work();
return 0;
}
```