题解：BZOJ4695 最佳女选手

wjr_jok · 2024-10-23 09:36:03 · 题解

和普通分块一样的套路，操作 1 和询问都是很常见的，考虑怎么实现操作 2,3 的同时保证询问的正确性。

发现操作 2,3 分别是底部推平和顶部推平，模拟一下可以发现会有很多区间被直接铺平，可以当作一个点来处理，用一个 tp 数组记录是否可以铺平即可，这样就可以节省很多时间，然后还要用到第二分块的做法：区间最大值小于推平操作底部或区间最小值大于推平操作顶部就直接铺平，反之如果最小值大于底部或最大值小于顶部就可以不操作。

由于打的是分块，所以每次修改散块时会影响到它所在的整块，需要把 ans,max,min 全部重新计算，并且对于整块要保证尽量不暴力修改，所以码量巨大，无缺省源 7.3KB，屎山勿喷。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+1;
int n,q,opt,l,r,s; 
int xl[N];
int x[N],y[N],fk[N],ans[N],maxx[N],minn[N],xg[N];
double tp[N];
signed main(){
    cin>>n;
    int cnt=sqrt(n);
    for(int i=1;i<=cnt;i++){
        x[i]=y[i-1]+1;
        y[i]=x[i]+cnt-1;
    }
    if(y[cnt]<n){
        cnt++;
        x[cnt]=y[cnt-1]+1;
        y[cnt]=n;
    }
    for(int i=1;i<=n;i++){
        cin>>xl[i];
    }
    for(int i=1;i<=n;i++){
        tp[i]=0.1,maxx[i]=-LLONG_MAX,minn[i]=LLONG_MAX;
        for(int j=x[i];j<=y[i];j++){
            fk[j]=i;
            ans[i]+=xl[j];
            maxx[i]=max(maxx[i],xl[j]);
            minn[i]=min(minn[i],xl[j]);
        }
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>opt>>l>>r;
        if(opt==1){
            cin>>s;
            if(tp[fk[l]]!=0.1){
                for(int j=x[fk[l]];j<=y[fk[l]];j++){
                    xl[j]=tp[fk[l]];
                }
                tp[fk[l]]=0.1;
            }
            if(xg[fk[l]]){
                for(int j=x[fk[l]];j<=y[fk[l]];j++){
                    xl[j]+=xg[fk[l]];
                }
                xg[fk[l]]=0;
            }
            for(int j=l;j<=min(r,y[fk[l]]);j++){
                xl[j]+=s;
                ans[fk[l]]+=s;
            }
            maxx[fk[l]]=-LLONG_MAX,minn[fk[l]]=LLONG_MAX;
            for(int j=x[fk[l]];j<=y[fk[l]];j++){
                maxx[fk[l]]=max(maxx[fk[l]],xl[j]);
                minn[fk[l]]=min(minn[fk[l]],xl[j]);
            }
            if(maxx[fk[l]]==minn[fk[l]]){
                tp[fk[l]]=maxx[fk[l]];
            }
            if(fk[l]!=fk[r]){
                if(tp[fk[r]]!=0.1){
                    for(int j=x[fk[r]];j<=y[fk[r]];j++){
                        xl[j]=tp[fk[r]];
                    }
                    tp[fk[r]]=0.1;
                }
                if(xg[fk[r]]){
                    for(int j=x[fk[r]];j<=y[fk[r]];j++){
                        xl[j]+=xg[fk[r]];
                    }
                    xg[fk[r]]=0;
                }
                for(int j=x[fk[r]];j<=r;j++){
                    xl[j]+=s;
                    ans[fk[r]]+=s;
                }
                maxx[fk[r]]=-LLONG_MAX,minn[fk[r]]=LLONG_MAX;
                for(int j=x[fk[r]];j<=y[fk[r]];j++){
                    maxx[fk[r]]=max(maxx[fk[r]],xl[j]);
                    minn[fk[r]]=min(minn[fk[r]],xl[j]);
                }
                if(maxx[fk[r]]==minn[fk[r]]){
                    tp[fk[r]]=maxx[fk[r]];
                }
            }
            for(int j=fk[l]+1;j<fk[r];j++){
                maxx[j]+=s;
                minn[j]+=s;
                ans[j]+=(y[j]-x[j]+1)*s;
                if(tp[j]!=0.1){
                    tp[j]+=s;
                }
                else{
                    xg[j]+=s;
                }
            }
        }
        if(opt==2){
            cin>>s;
            if(tp[fk[l]]!=0.1){
                for(int j=x[fk[l]];j<=y[fk[l]];j++){
                    xl[j]=tp[fk[l]];
                }
                tp[fk[l]]=0.1;
            }
            if(xg[fk[l]]){
                for(int j=x[fk[l]];j<=y[fk[l]];j++){
                    xl[j]+=xg[fk[l]];
                }
                xg[fk[l]]=0;
            }
            for(int j=l;j<=min(r,y[fk[l]]);j++){
                ans[fk[l]]-=xl[j];
                xl[j]=max(xl[j],s);
                ans[fk[l]]+=xl[j];
            }
            maxx[fk[l]]=-LLONG_MAX,minn[fk[l]]=LLONG_MAX;
            for(int j=x[fk[l]];j<=y[fk[l]];j++){
                maxx[fk[l]]=max(maxx[fk[l]],xl[j]);
                minn[fk[l]]=min(minn[fk[l]],xl[j]);
            }
            if(maxx[fk[l]]==minn[fk[l]]){
                tp[fk[l]]=maxx[fk[l]];
            }
            if(fk[l]!=fk[r]){
                if(tp[fk[r]]!=0.1){
                    for(int j=x[fk[r]];j<=y[fk[r]];j++){
                        xl[j]=tp[fk[r]];
                    }
                    tp[fk[r]]=0.1;
                }
                if(xg[fk[r]]){
                    for(int j=x[fk[r]];j<=y[fk[r]];j++){
                        xl[j]+=xg[fk[r]];
                    }
                    xg[fk[r]]=0;
                }
                for(int j=x[fk[r]];j<=r;j++){
                    ans[fk[r]]-=xl[j];
                    xl[j]=max(xl[j],s);
                    ans[fk[r]]+=xl[j];
                }
                maxx[fk[r]]=-LLONG_MAX,minn[fk[r]]=LLONG_MAX;
                for(int j=x[fk[r]];j<=y[fk[r]];j++){
                    maxx[fk[r]]=max(maxx[fk[r]],xl[j]);
                    minn[fk[r]]=min(minn[fk[r]],xl[j]);
                }
                if(maxx[fk[r]]==minn[fk[r]]){
                    tp[fk[r]]=maxx[fk[r]];
                }
            }
            for(int j=fk[l]+1;j<fk[r];j++){
                if(tp[j]!=0.1){
                    tp[j]=maxx[j]=minn[j]=max(tp[j],(double)s);
                    ans[j]=(y[j]-x[j]+1)*tp[j];
                }
                else if(maxx[j]<=s){
                    tp[j]=maxx[j]=minn[j]=s;
                    xg[j]=0;
                    ans[j]=(y[j]-x[j]+1)*s;
                }
                else if(minn[j]<s){
                    if(xg[j]){
                        for(int k=x[j];k<=y[j];k++){
                            xl[k]+=xg[j];
                        }
                        xg[j]=0;
                    }
                    maxx[j]=-LLONG_MAX,minn[j]=LLONG_MAX;
                    for(int k=x[j];k<=y[j];k++){
                        ans[j]-=xl[k];
                        xl[k]=max(xl[k],s);
                        minn[j]=min(minn[j],xl[k]);
                        maxx[j]=max(maxx[j],xl[k]);
                        ans[j]+=xl[k];
                    }
                    if(maxx[j]==minn[j]){
                        tp[j]=maxx[j];
                    }
                }
            }
        }
        if(opt==3){
            cin>>s;
            if(tp[fk[l]]!=0.1){
                for(int j=x[fk[l]];j<=y[fk[l]];j++){
                    xl[j]=tp[fk[l]];
                }
                tp[fk[l]]=0.1;
            }
            if(xg[fk[l]]){
                for(int j=x[fk[l]];j<=y[fk[l]];j++){
                    xl[j]+=xg[fk[l]];
                }
                xg[fk[l]]=0;
            }
            for(int j=l;j<=min(r,y[fk[l]]);j++){
                ans[fk[l]]-=xl[j];
                xl[j]=min(xl[j],s);
                ans[fk[l]]+=xl[j];
            }
            maxx[fk[l]]=-LLONG_MAX,minn[fk[l]]=LLONG_MAX;
            for(int j=x[fk[l]];j<=y[fk[l]];j++){
                maxx[fk[l]]=max(maxx[fk[l]],xl[j]);
                minn[fk[l]]=min(minn[fk[l]],xl[j]);
            }
            if(maxx[fk[l]]==minn[fk[l]]){
                tp[fk[l]]=maxx[fk[l]];
            }
            if(fk[l]!=fk[r]){
                if(tp[fk[r]]!=0.1){
                    for(int j=x[fk[r]];j<=y[fk[r]];j++){
                        xl[j]=tp[fk[r]];
                    }
                    tp[fk[r]]=0.1;
                }
                if(xg[fk[r]]){
                    for(int j=x[fk[r]];j<=y[fk[r]];j++){
                        xl[j]+=xg[fk[r]];
                    }
                    xg[fk[r]]=0;
                }
                for(int j=x[fk[r]];j<=r;j++){
                    ans[fk[r]]-=xl[j];
                    xl[j]=min(xl[j],s);
                    ans[fk[r]]+=xl[j];
                }
                maxx[fk[r]]=-LLONG_MAX,minn[fk[r]]=LLONG_MAX;
                for(int j=x[fk[r]];j<=y[fk[r]];j++){
                    maxx[fk[r]]=max(maxx[fk[r]],xl[j]);
                    minn[fk[r]]=min(minn[fk[r]],xl[j]);
                }
                if(maxx[fk[r]]==minn[fk[r]]){
                    tp[fk[r]]=maxx[fk[r]];
                }
            }
            for(int j=fk[l]+1;j<fk[r];j++){
                if(tp[j]!=0.1){
                    tp[j]=maxx[j]=minn[j]=min(tp[j],(double)s);
                    ans[j]=(y[j]-x[j]+1)*tp[j];
                }
                else if(minn[j]>=s){
                    maxx[j]=minn[j]=s;
                    tp[j]=s;
                    xg[j]=0;
                    ans[j]=(y[j]-x[j]+1)*s;
                }
                else if(maxx[j]>s){
                    if(xg[j]){
                        for(int k=x[j];k<=y[j];k++){
                            xl[k]+=xg[j];
                        }
                        xg[j]=0;
                    }
                    maxx[j]=-LLONG_MAX,minn[j]=LLONG_MAX;
                    for(int k=x[j];k<=y[j];k++){
                        ans[j]-=xl[k];
                        xl[k]=min(xl[k],s);
                        maxx[j]=max(maxx[j],xl[k]);
                        minn[j]=min(minn[j],xl[k]);
                        ans[j]+=xl[k];
                    }
                    if(maxx[j]==minn[j]){
                        tp[j]=maxx[j];
                    }
                }
            }
        }
        if(opt==4){
            int cnt=0;
            for(int j=l;j<=min(r,y[fk[l]]);j++){
                if(tp[fk[l]]!=0.1){
                    cnt+=tp[fk[l]];
                }
                else{
                    cnt+=xl[j]+xg[fk[l]];
                }
            }
            if(fk[l]!=fk[r]){
                for(int j=x[fk[r]];j<=r;j++){
                    if(tp[fk[r]]!=0.1){
                        cnt+=tp[fk[r]];
                    }
                    else{
                        cnt+=xl[j]+xg[fk[r]];
                    }
                }
            }
            for(int j=fk[l]+1;j<fk[r];j++){
                cnt+=ans[j];
            }
            cout<<cnt<<endl;
        }
        if(opt==5){
            int cnt=-LLONG_MAX;
            for(int j=l;j<=min(r,y[fk[l]]);j++){
                if(tp[fk[l]]!=0.1){
                    cnt=max(cnt,(int)tp[fk[l]]);
                }
                else{
                    cnt=max(cnt,xl[j]+xg[fk[l]]);
                }
            }
            if(fk[l]!=fk[r]){
                for(int j=x[fk[r]];j<=r;j++){
                    if(tp[fk[r]]!=0.1){
                        cnt=max(cnt,(int)tp[fk[r]]);
                    }
                    else{
                        cnt=max(cnt,xl[j]+xg[fk[r]]);
                    }
                }
            }
            for(int j=fk[l]+1;j<fk[r];j++){
                cnt=max(cnt,maxx[j]);
            }
            cout<<cnt<<endl;
        }
        if(opt==6){
            int cnt=LLONG_MAX;
            for(int j=l;j<=min(r,y[fk[l]]);j++){
                if(tp[fk[l]]!=0.1){
                    cnt=min(cnt,(int)tp[fk[l]]);
                }
                else{
                    cnt=min(cnt,xl[j]+xg[fk[l]]);
                }
            }
            if(fk[l]!=fk[r]){
                for(int j=x[fk[r]];j<=r;j++){
                    if(tp[fk[r]]!=0.1){
                        cnt=min(cnt,(int)tp[fk[r]]);
                    }
                    else{
                        cnt=min(cnt,xl[j]+xg[fk[r]]);
                    }
                }
            }
            for(int j=fk[l]+1;j<fk[r];j++){
                cnt=min(cnt,minn[j]);
            }
            cout<<cnt<<endl;
        }
    }
    return 0;
}