Link

CF1884 C Medium Design

Question

有一个数组 \(a_1...a_m\) 和 \(N\) 个区间 \(L_i,R_i\) 我们可以选一部分区间，使得 \([a_{L_i},a_{R_i}]\) 的每一个值都 \(+1\)

求 \(max(a)-min(a)\) 的最大值

Solution

我们先考虑一个结论

如果最大值和最小值在同一个区间内，那么这根线就没有价值了，加和不加都一样

那么我们考虑损失最小的那个点，也就是 \(1\) 和 \(M\) ，也就是说，最小值在两端

所以先把数离散化，然后用树状数组统计每个点覆盖的区间数就好了

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

int T,N,M,tot,c[maxn<<1];
map<int,int> mp;
map<int,int>::iterator it;
struct line{
    int L,R;
}a[maxn];

void add_x(int x,int w){
    for(int i=x;i<=tot+1;i+=i&-i)
        c[i]+=w;
    return ;
}

int get_x(int x){
    int ret=0;
    for(int i=x;i>0;i-=i&-i)
        ret+=c[i];
    return ret;
}

int check(int pos){
    memset(c,0,sizeof c);
    for(int i=1;i<=N;i++){
        if(mp[a[i].L]<=pos&&mp[a[i].R]>=pos) continue;
        add_x(mp[a[i].L],1);add_x(mp[a[i].R]+1,-1);
    }
    int ans=0;
    for(int i=1;i<=tot;i++){
        ans=max(ans,get_x(i));
    }
    return ans;
}

int main(){
    // freopen("C.in","r",stdin);
    // freopen("C.out","w",stdout);
    T=read();
    while(T--){
        mp.clear();
        N=read();M=read();
        for(int i=1;i<=N;i++){
            a[i].L=read();a[i].R=read();
            mp[a[i].L]=1;mp[a[i].R]=1;
        }
        mp[1]=1;mp[M]=1;
        tot=0;
        for(it=mp.begin();it!=mp.end();++it){
            mp[(*it).first]=++tot;
        }
        printf("%d\n",max(check(mp[1]),check(mp[M])));
    }
    return 0;
}