cf#690(div3)

F. The Treasure of The Segments

链接

题意

有n条线段（1<= n <= 2e5）,线段两端L，R(1<= L <= R <= 1e9)

问删掉最小数量的线段，使所有的线段不重合？

题解一

对于线段i来说，需要删掉T[j] 大于 a[i].s 的 以及 S[j]大于a[i].t。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long ll;
const int MAX = 2e5 + 5;struct line{
    ll  s, t;
};line a[MAX]; 
ll S[MAX], T[MAX];int main() {
    int tt;scanf("%d", &tt);while(tt--) {
    int n;scanf("%d", &n);for (int i = 0; i < n; i++)  {
    scanf("%lld%lld", &a[i].s, &a[i].t);S[i] = a[i].s;T[i] = a[i].t;}sort(S, S + n);sort(T, T + n);int maxx = MAX;for(int i = 0; i < n; i++) {
    int ans = 0;ans += (lower_bound(T, T + n, a[i].s) - T);ans += (n - (upper_bound(S, S + n, a[i].t) - S));maxx = min(maxx, ans);}printf("%d\n", maxx);}
}

题解二

问题转化为 n - 重合数量最多

按照L排序，从小到大，对于第i个线段，把所有L小于t的压入优先队列（优先队列按照R排序），此时bit函数第i为覆盖的是优先队列的大小，前i位因为新加入i根线段，所有值++。如果最小R值（优先队列top）小于t，弹出，取这个弹出线段的覆盖线段max值。

由于 LR 太大 ==》 离散化

区间加减 ==》树状数组

注意：

树状数组最好从1开始（个人认为） 这样的话，离散化后值为 位置 + 1

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int MAX = 2e5 + 12;struct line {
    ll s, t, n;bool operator<(const line &a)const {
    return a.t < t;}
};int bit[MAX + 10];int sum(int i) {
    int ans = 0;while(i) {
    ans += bit[i];i -= i & -i;}return ans;
}
void add(int k, int x) {
    while(k < MAX) {
    bit[k] += x;k += k & -k;}
}bool cmp(line a, line b) {
    if(a.s != b.s) return a.s < b.s;return a.t < b.t;
}void LRadd(int L, int R, int x) {
    add(L, x);add(R + 1, -x);
}vector<ll> v;
line a[MAX];
int main() {
    int T;scanf("%d", &T);while(T--) {
    v.clear();int n;scanf("%d", &n);for(int i = 1; i <= n; i++) bit[i] = 0;for(int i = 1; i <= n; i++) {
    scanf("%lld %lld", &a[i].s, &a[i].t);v.push_back(a[i].s);v.push_back(a[i].t);}sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());for(int i = 1; i <= n; i++) {
    a[i].s = lower_bound(v.begin(), v.end(), a[i].s) - v.begin() + 1;a[i].t = lower_bound(v.begin(), v.end(), a[i].t) - v.begin() + 1;}sort(a + 1, a + 1 + n, cmp);for(int i = 1; i <= n; i++) a[i].n = i;priority_queue<line>que;int pos = 1;//对于t来说int maxx = -1;for(int t = 1; t < 2 * n + 10; t++) {
    while(pos <= n && a[pos].s <= t) {
    que.push(a[pos]);LRadd(1, pos - 1, 1);LRadd(pos, pos, que.size());pos++;}while(1) {
    if(que.top().t > t || que.empty()) break;maxx = max(maxx, sum(que.top().n));que.pop();}}printf("%d\n", n - maxx);}
}