CF1884C Medium Design 题解

· · 题解

一道不错的用线段树考虑贡献的题。

这里提供一种和官方题解思路不太一样的方法。

简要题意

给定 n 个区间，和一个长度为 m 且初始值全部为 0 的序列，任选其中的一些区间，在序列中进行区间加 1 操作，要使操作后序列的最大值与最小值之差最大，求出这个最大的差值。

思路

如果操作后最大值和最小值的位置确定，考虑每个区间，发现只有仅覆盖了最大值的区间会对答案产生贡献，其他区间（即覆盖了最小值的区间）则不用考虑，故可以反过来枚举所有最小值可能在的位置，对于每一个最小值的位置，可能的答案就是所有未覆盖该位置的区间进行区间加 1 后得到的序列里的最大值（即把最小值当成 0 考虑，每次区间加如果加到了最小值上一定不会使答案变大，故直接不考虑覆盖了最小值的区间），最后答案就是所有最大值里取最大。

显然这是个 RMQ 问题，用线段树维护。但每次枚举最小值直接暴力区间修改不覆盖最小值的区间复杂度无法接受，所以可以换一下思路，先把所有区间都覆盖一遍，然后从左到右枚举最小值的时候考虑每个区间的贡献：枚举到点 i 时，对于所有左端点在 i 的区间进行区间减 1，即这些区间会覆盖 i 及后面的一些位置，对于这些位置需要消除掉覆盖它们的区间的影响；同理，对于所有右端点在 i 的区间进行区间加 1，加入这些区间对后面位置的影响（注意实现时加入影响的操作要在得到该位置的答案之后，因为该位置还在这些区间内，不能被这些区间贡献）。实现时只需要把区间分别挂到其左右端点上，用两个 vector 数组存即可（详见代码）。

还需要注意的一点，由于区间范围很大，需要离散化，离散化之后会使原本不相邻的两个区间变成相邻的，这会漏掉一些情况，当然可以人为在离散化对不相邻的区间之间增加一个位置，但实现起来稍微有点麻烦，而可以发现这道题如果存在不相邻的区间，就意味着序列的最小值一定是 0，答案就是对全部区间进行区间加以后的最大值，只需特判即可（注意序列最左边或最右边没被覆盖的情况需要单独考虑）。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=500010;

struct Seg{int l,r;}seg[N];
bool cmp(Seg a,Seg b){return a.l==b.l?a.r<b.r:a.l<b.l;}
struct Node{int ma,tag;}tr[N<<2];
vector<int> dl[N],dr[N];//分别存左、右端点在 i 的区间编号 

inline void pushup(int p){tr[p].ma=max(tr[p<<1].ma,tr[p<<1|1].ma);}
inline void addtag(int p,int d){tr[p].tag+=d,tr[p].ma+=d;}
inline void pushdown(int p)
{
    if(tr[p].tag)
    {
        addtag(p<<1,tr[p].tag),addtag(p<<1|1,tr[p].tag);
        tr[p].tag=0;
    }
}
void build(int p,int pl,int pr)//只是方便对整棵树清零 
{
    tr[p].ma=tr[p].tag=0;
    if(pl==pr) return;
    int mid=pl+pr>>1;
    build(p<<1,pl,mid),build(p<<1|1,mid+1,pr);
}
void update(int p,int pl,int pr,int L,int R,int d)
{
    if(L<=pl&&pr<=R)
    {
        addtag(p,d);
        return;
    }
    pushdown(p);
    int mid=pl+pr>>1;
    if(mid>=L) update(p<<1,pl,mid,L,R,d);
    if(mid<R) update(p<<1|1,mid+1,pr,L,R,d);
    pushup(p);
}

int t,m,n,a[N];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        int res=0;
        bool k=0,ll=1,rr=1;//k:是否存在不连续的区间，ll:最左边没有被覆盖，rr:最右边没有被覆盖 
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i) 
            scanf("%d%d",&seg[i].l,&seg[i].r),a[(i-1)*2+1]=seg[i].l,a[(i-1)*2+2]=seg[i].r,rr&=(seg[i].r<m),ll&=(seg[i].l>1);

        k=(ll||rr);//只要两边有空着的就计入特判的情况 
        sort(seg+1,seg+1+n,cmp);//对区间排序，方便判断是否存在没有被任何一个区间覆盖的位置 
        int rmax=1; 
        for(int i=1;i<=n;++i)
        {
            if(seg[i].l>rmax+1) k=1;//左边的区间最右的端点也与目前左端点间隔了距离 ，即找到了一个没有被任何区间覆盖的位置 
            while(seg[i].l==seg[i+1].l) ++i;//左端点相同的区间找到右端点最右的一个（已经按右端点为第二关键字排序） 
            rmax=max(rmax,seg[i].r);//更新左边区间最右端点的位置，注意一定要取max，因为左端点更靠右的区间右端点可能反而小 
        }

        //离散化 
        sort(a+1,a+1+2*n);      
        int cnt=unique(a+1,a+1+2*n)-(a+1);  

        //多测清空 
        build(1,1,cnt); 
        for(int i=1;i<=cnt;++i) dl[i].clear(),dr[i].clear();

        //离散化后重新赋值，顺便把所有区间进行覆盖，和记录左右端点位置对应的区间编号 
        for(int i=1;i<=n;++i)
            seg[i].l=lower_bound(a+1,a+1+cnt,seg[i].l)-a,seg[i].r=lower_bound(a+1,a+1+cnt,seg[i].r)-a,
            update(1,1,cnt,seg[i].l,seg[i].r,1),dl[seg[i].l].push_back(i),dr[seg[i].r].push_back(i);

        if(k){printf("%d\n",tr[1].ma);continue;}//特判存在没有被任何区间覆盖的位置的情况

        for(int i=1;i<=cnt;++i)
        {
            for(auto j:dl[i]) update(1,1,cnt,seg[j].l,seg[j].r,-1);//消除覆盖了这个位置的区间的影响 
            res=max(res,tr[1].ma);//更新最大的答案 
            for(auto j:dr[i]) update(1,1,cnt,seg[j].l,seg[j].r,1);//加上没有覆盖这个位置的区间的影响，注意该操作要在更新答案之后 
        }
        printf("%d\n",res);
    }
    return 0;
}

一个朋友的另一种做法