Charging

题意

数轴上有一共个点，个区间分别是。
设为所选取的区间数量，为所有所选取的区间的交集长度。
求的最大值。

最优解标程为线段树，复杂度为

qingzhu思路

1. 将所有线段按左端点升序排序。
2. 枚举区间：枚举左端点，二分枚举右端点。
3. 收纳所有左端点小于等于当前的的线段的右端点。即线段里有可能有的线段。
4. 如果收纳集合内存在至少个大于等于的右端点，那么就认为必定可行，于是继续向右搜索更大的。

时间复杂度

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &(x))
#define pr(x) printf("%d\n", (x))
using namespace std;
typedef pair<int, int> pii;
const int N = 3e5 + 7;
#define lowbit(x) ((x) & (-x))
int tree[N];
inline void add(int i) {
    for (int pos = i; pos < N; pos += lowbit(pos)) ++tree[pos];
}
inline int query(int n) {
    int ans = 0;
    for (int pos = n; pos; pos -= lowbit(pos)) ans += tree[pos];
    return ans;
}
pii a[N];
int main() {
    int n, m;
    sc(n), sc(m);
    for (int i = 0; i < m; ++i) sc(a[i].first), sc(a[i].second);
    sort(a, a + m);
    int ans = 0;
    for (int L = 1, p = 0; L <= n; ++L) {
        while (p < m && a[p].first <= L) add(a[p++].second);
        int left = L, right = n, R = 0;
        while (left <= right) {
            int mid = left + right >> 1;
            int tot = p - query(mid - 1);
            if (tot >= mid - L + 1)
                left = mid + 1, R = mid;
            else
                right = mid - 1;
        }
        ans = max(ans, R - L + 1);
    }
    pr(ans);
    return 0;
}

大法师思路

1. 因为答案必定在中，所以可以考虑二分
2. 将所有长度满足的区间收纳进一个集合，然后对右端点按照从大到小排序
3. 枚举所有线段，用BIT维护左端点，如果数量满足要求check就返回1。

时间复杂度

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 3e5 + 5;
int n, m;
int tree[maxn];
int lowbit(int x) { return x & (-x); }
void add(int x, int val) {
    for (int i = x; i <= n; i += lowbit(i)) tree[i] += val;
}
int Find(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tree[i];
    return res;
}
struct node {
    int l, r;
    int len;
} p[maxn], s[maxn];
int tot = 0;
bool cmp(node a, node b) { return a.r < b.r; }
bool check(int val) {
    memset(tree, 0, sizeof(tree));
    tot = 0;
    for (int i = 1; i <= m; i++) {
        if (p[i].len >= val) {
            tot++;
            s[tot].l = p[i].l, s[tot].r = p[i].r;
            add(p[i].l, 1);
        }
    }
    sort(s + 1, s + 1 + tot, cmp);
    for (int i = 1; i <= tot; i++) {
        int v = Find(s[i].r - val + 1);
        add(s[i].l, -1);
        if (v >= val) return true;
    }
    return false;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> p[i].l >> p[i].r;
        p[i].len = p[i].r - p[i].l + 1;
    }
    int l = 1, r = m;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid))
            l = mid;
        else {
            r = mid - 1;
        }
    }
    printf("%d\n", l);
    return 0;
}

吴博雄思路

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &(x))
#define pr(x) printf("%d\n", x)
#define L first
#define R second
using namespace std;
const int N = 3e5 + 7;
pair<int, int> seg[N];
int main() {
    int n, m;
    sc(n), sc(m);
    for (int i = 0; i < m; ++i) sc(seg[i].L), sc(seg[i].R);
    sort(seg, seg + m);  //线段按照左端点从小到大排序
    int ans = 0, cnt = 0;
    priority_queue<int, vector<int>, greater<int>> q;  //小顶堆维护区间右端点
    for (int i = 0; i < m; ++i) {  //交集的左端点必定是某个区间的左端点
        q.push(seg[i].R), ++cnt;  //交集的右端点必定是某个区间的右端点
        while (cnt > q.top() - seg[i].L + 1) q.pop(), --cnt;
        //本行是理解此种做法的重点：cnt即是tot，而前值则是交集长度
        //不可行的交集求长度为负值
        ans = max(ans, cnt);
    }
    pr(ans);
    return 0;
}
/*
1 3
5 6
5 9
*/