CF1108E Array and Segments解题报告

解题报告

CF1108E1 Array and Segments (Easy version)&CF1108E2 Array and Segments (Hard version)解题报告:

更好的阅读体验

题意

• 给定一个长度为$n$的序列$a$,你可以进行$m$次操作中的任意一些操作,每个操作为$[l,r]$,表示让区间$[l,r]$减一,求使得序列极差最大的操作方案.
• Easy Version:$1\leqslant n\leqslant 300,0\leqslant m\leqslant 300$.
• Hard Version:$1\leqslant n\leqslant 10^5,0\leqslant m\leqslant 300$.

分析

首先,因为极差=最大值-最小值,而一个同时包含最大值和最小值的区间如果不改变最大值和最小值的位置,是不会对极差造成影响的,因此我们有一个初步的想法:

我们枚举最大值位置,然后进行所有不包含最大值位置的操作,并得到最小值,最后将所有的极差取$\max$.

这样做的复杂度是$O(nq\log n)$的,可以通过Easy Version.

优化也很简单,我们发现上述算法枚举的操作区间或起来都不是全集(要给最大值留位置),很容易想到枚举没有进行的操作,因为操作区间或不是全集,因此没有进行的操作区间与起来不为空集,这样至少会有一个位置没有操作过,可以成为最大值.

我们先加入所有区间,然后枚举每一个位置,先撤销以这个位置开始的操作,求得一个极差,然后再重新进行以这个位置结束的操作,这样我们就能保证求极差时撤销的区间都包含当前位置.

只需要写一个区间加,区间$\min/\max$的线段树就好了.

时间复杂度:$O(n+m\log n)$,可以通过Hard Version.

代码

#include<stdio.h>
#include<vector>
#define inf 1000000000
using namespace std;
const int maxn=100005,maxk=maxn<<2;
int n,m,ans,pos,cnt;
int a[maxn],lc[maxk],rc[maxk],maxx[maxk],minn[maxk],lazy[maxk],xx[maxn],yy[maxn];
vector<int>l[maxn],r[maxn];
inline void pushup(int now){
    maxx[now]=max(maxx[lc[now]],maxx[rc[now]]);
    minn[now]=min(minn[lc[now]],minn[rc[now]]);
}
inline void getlazy(int now,int v){
    maxx[now]+=v,minn[now]+=v,lazy[now]+=v;
}
inline void pushdown(int now){
    if(lazy[now]==0)
        return ;
    getlazy(lc[now],lazy[now]),getlazy(rc[now],lazy[now]);
    lazy[now]=0;
}
void build(int l,int r,int now){
    if(l==r){
        maxx[now]=minn[now]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    lc[now]=now<<1,rc[now]=now<<1|1;
    build(l,mid,lc[now]),build(mid+1,r,rc[now]);
    pushup(now);
}
void update(int l,int r,int now,int L,int R,int v){
    if(L<=l&&r<=R){
        getlazy(now,v);
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(now);
    if(L<=mid)
        update(l,mid,lc[now],L,R,v);
    if(mid<R)
        update(mid+1,r,rc[now],L,R,v);
    pushup(now);
}
int main(){
    maxx[0]=-inf,minn[0]=inf;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,n,1);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        xx[i]=x,yy[i]=y;
        l[x].push_back(y),r[y].push_back(x);
        update(1,n,1,x,y,-1);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<l[i].size();j++)
            update(1,n,1,i,l[i][j],1);
        if(maxx[1]-minn[1]>ans)
            ans=maxx[1]-minn[1],pos=i;
        for(int j=0;j<r[i].size();j++)
            update(1,n,1,r[i][j],i,-1);
    }
    printf("%d\n",ans);
    for(int i=1;i<=m;i++)
        if(xx[i]>pos||yy[i]<pos)
            cnt++;
    printf("%d\n",cnt);
    for(int i=1;i<=m;i++)
        if(xx[i]>pos||yy[i]<pos)
            printf("%d ",i);
    puts("");
    return 0;
}