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);
	}
}