Medium Design

问题描述

给 \(n\) 个区间, 你可以任意选择给出区间的一部分, 换句话说, 你可以任意选择一个给出区间的所有子集(包括空集), 然后你要进行以下的操作 :

• 对于选择的区间, 我们要进行整体加操作, 即如果你选择了 \([l_i, r_i]\), 那么对于所有的 \(a_j, j∈[l_i, r_i]\) 都要加 \(1\), 对于你没有选择的区间, 不需要进行操作
• 在所有操作完成之后, 你需要给出 \(max_a - min_a\) 的最大值

思路

对于这个问题, 有两个解决方案可以做, 首先讨论第一种, 贪心
观察性质, 发现我们先钦定数组的最大值和最小值的位置, 那么我们要进行区间加操作的时候, 会出现以下三种情况:

• 区间不包含最大值的位置, 舍去
• 区间包含最大值的位置且不包含最小值的位置, 加入
• 区间包含最大值和最小值的位置, 可加入可不加入

也就是说, 我们只需要选择只包含最大值的位置的区间即可, 由于这个性质的出现, 那么如果我们的最小值 \(x\) 设置在数组中间, 也就是说包含中间位置的区间一律不能选, 即区间必须要在最小值的左侧或者右侧, 那么假设最后的最大值位置在左侧, 即中间的右侧区间都需要舍去, 那么如果此时让 \(x\) 向右移, 答案会变多或不变. 最大值位置在右侧也是同理

那么无论如何, \(x\) 在中间显然是不如在两侧端点的, 也就是只需要钦定两侧端点为最小值点, 然后进行模拟, 看看那一侧的答案更大即可, 需要离散化

// Retired?
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
void solve(){

    int n, m; cin >> n >> m;

    vector<int> v;
    vector<pair<int, int>> p(n + 1);
    for(int i = 1; i <= n; i++){
        int l, r; cin >> l >> r;
        v.push_back(l), v.push_back(r);
        p[i] = {l, r};
    }
    
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    map<int, int> mp;
    int tot = 0;
    for(auto x : v) mp[x] = ++tot;

    vector<int> c1(tot + 2), c2(tot + 2);
    for(int i = 1; i <= n; i++){
        auto [l, r] = p[i];
        if(l != 1) c1[mp[l]]++, c1[mp[r] + 1]--;
        if(r != m) c2[mp[l]]++, c2[mp[r] + 1]--;
    }

    int res = 0, mx1 = LLONG_MIN, mx2 = LLONG_MIN;
    for(int i = 1; i <= tot; i++){
        c1[i] += c1[i - 1], c2[i] += c2[i - 1];
        mx1 = max(mx1, c1[i]), mx2 = max(mx2, c2[i]);
        res = max(res, max(mx1, mx2));
    }

    cout << res << '\n';

}
signed main(){
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t;t = 1;while(t--)solve();
}

另一种方法就是枚举所有的点为最大值点, 同样需要离散化, 然后从小到大加入区间, 由于上面的讨论, 对于这个点有用的区间加进去一定不劣, 那么我们就把所有有用的区间加进来, 然后对于没用的区间都需要删除, 也就是说我们需要按照左端点进行排序, 然后维护一个右端点的优先队列, 这样可以保证不重复加入区间, 对于查询最小值, 显然用动态 \(RMQ\) 问题解决, 树状数组或者线段树均可

// Retired?
#include <bits/stdc++.h>
#define int long long
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
struct node{
    int l, r;
    bool operator<(const node &w) const{
        return r > w.r;
    }
};
struct SegmentTree{
    struct Seg{
        int l, r, max, min, add;
    };
    
    int n;
    vector<Seg> tr;
    SegmentTree(int n_) : n(n_), tr(n_ << 3) {}
    
    void work(int u, int x){
        tr[u].max += x, tr[u].min += x, tr[u].add += x;
    }   

    Seg merge(Seg l, Seg r){
        Seg res;
        res.l = l.l, res.r = r.r;
        res.max = max(l.max, r.max);
        res.min = min(l.min, r.min);
        return res;
    }

    void pushdown(int u){
        if(tr[u].add){
            work(ls, tr[u].add), work(rs, tr[u].add);
            tr[u].add = 0;
        }
    }

    void pushup(int u){
        tr[u].max = max(tr[ls].max, tr[rs].max);
        tr[u].min = min(tr[ls].min, tr[rs].min);
    }

    void build(int u, int l, int r){
        if(l == r){
            tr[u] = {l, r, 0, 0, 0};
            return;
        }
        tr[u] = {l, r, 0, 0, 0};
        int mid = l + r >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
        pushup(u);
    }

    void add(int u, int l, int r, int x){
        if(tr[u].l >= l && tr[u].r <= r){
            work(u, x);
            return;
        }
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) add(ls, l, r, x);
        if(r > mid) add(rs, l, r, x);
        pushup(u);
    }

    Seg query(int u, int l, int r){
        if(tr[u].l >= l && tr[u].r <= r){
            return tr[u];
        }
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        Seg res = {0, 0, 0, 0, 0};
        if(l <= mid) res = query(ls, l, r);
        if(r > mid) res = merge(res, query(rs, l, r));
        return res;
    }

};
void solve(){

    int n, m; cin >> n >> m;

    vector<int> v;
    vector<node> p(n + 1);
    for(int i = 1; i <= n; i++){
        int l, r; cin >> l >> r;
        v.push_back(l), v.push_back(r);
        p[i] = {l, r};
    }
    v.push_back(1), v.push_back(m);
    
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    map<int, int> mp;
    int tot = v.size();
    for(int i = 1; i <= tot; i++) mp[v[i - 1]] = i;

    vector<int> c(tot + 2);
    for(int i = 1; i <= n; i++){
        auto &[l, r] = p[i];
        l = mp[l], r = mp[r];
        c[l]++, c[r + 1]--;
    }

    sort(p.begin() + 1, p.end(), [](node a, node b){
        return a.l < b.l;
    });

    priority_queue<node> que;
    SegmentTree Tree(tot);
    Tree.build(1, 1, tot);

    int cur = 1, res = LLONG_MIN;
    for(int i = 1; i <= tot; i++){
        c[i] += c[i - 1];
        while(cur <= n && p[cur].l <= i){
            Tree.add(1, p[cur].l, p[cur].r, 1);
            que.push(p[cur++]);
        }
        while(!que.empty() && que.top().r < i){
            Tree.add(1, que.top().l, que.top().r, -1);
            que.pop();
        }
        res = max(res, c[i] - Tree.tr[1].min);
    }   
    
    cout << res << '\n';

}
signed main(){
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t;cin>>t;while(t--)solve();
}