题解：[ABC256Ex] I like Query Problem

· · 题解

可以纯分块。

直接分块肯定会炸，所以套用一点势能线段树的思想，在块内所有值相等时把它当成一个点来维护，对应代码中的 tp 数组。

对于操作 1，散块直接修改，然后遍历这个块，修改 tp 的状态（是否均为同一值）。整块 tp 若不为 -1（所赋初始值）就直接修改 tp，否则就暴力遍历整块，然后更新 tp（只需看块内最小值是否等于最大值）。

对于操作 2，散块仍然只能直接修改，操作不变，而整块可以直接修改 tp 为 x（推平的值）。

询问时跟普通分块一样直接统计答案即可。

需要注意的是修改分块由于要保证 tp 的正确性，需要遍历整个块来更新，以及 tp 与原序列 xl 中所存的值的优先级。

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],tp[N];
signed main(){
    cin>>n>>q;
    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]=-1,minn[i]=INT_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]);
        }
    }
    for(int i=1;i<=q;i++){
        cin>>opt>>l>>r;
        if(opt==1){
            cin>>s;
            if(tp[fk[l]]){
                if(tp[fk[l]]!=-1){
                    for(int j=x[fk[l]];j<=y[fk[l]];j++){
                        xl[j]=tp[fk[l]];
                    }
                }
                for(int j=l;j<=min(r,y[fk[l]]);j++){
                    ans[fk[l]]-=xl[j];
                    xl[j]/=s;
                    ans[fk[l]]+=xl[j];
                }
                maxx[fk[l]]=0,minn[fk[l]]=INT_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]]=xl[l];
                }
                else{
                    tp[fk[l]]=-1;
                }
            }
            if(fk[l]!=fk[r]){
                if(tp[fk[r]]){
                    if(tp[fk[r]]!=-1){
                        for(int j=x[fk[r]];j<=y[fk[r]];j++){
                            xl[j]=tp[fk[r]];
                        }
                    }
                    for(int j=x[fk[r]];j<=r;j++){
                        ans[fk[r]]-=xl[j];
                        xl[j]/=s;
                        ans[fk[r]]+=xl[j];
                    }
                    maxx[fk[r]]=0,minn[fk[r]]=INT_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]]=xl[r];
                    }
                    else{
                        tp[fk[r]]=-1;
                    }
                }
            }
            for(int j=fk[l]+1;j<fk[r];j++){
                maxx[j]/=s;
                minn[j]/=s;
                if(tp[j]!=-1){
                    if(tp[j]){
                        tp[j]/=s;
                        ans[j]=(y[j]-x[j]+1)*tp[j];
                    }
                }
                else{
                    if(maxx[j]==minn[j]){
                        tp[j]=maxx[j];
                        ans[j]=(y[j]-x[j]+1)*tp[j];
                    }
                    else{
                        for(int k=x[j];k<=y[j];k++){
                            ans[j]-=xl[k];
                            xl[k]/=s;
                            ans[j]+=xl[k];
                        }
                    }
                }
            }
        }
        if(opt==2){
            cin>>s;
            if(tp[fk[l]]!=-1){
                for(int j=x[fk[l]];j<=y[fk[l]];j++){
                    xl[j]=tp[fk[l]];
                }
            }
            for(int j=l;j<=min(r,y[fk[l]]);j++){
                ans[fk[l]]-=xl[j];
                xl[j]=s;
                ans[fk[l]]+=xl[j];
            }
            maxx[fk[l]]=minn[fk[l]]=s;
            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]]=xl[l];
            }
            else{
                tp[fk[l]]=-1;
            }
            if(fk[l]!=fk[r]){
                if(tp[fk[r]]!=-1){
                    for(int j=x[fk[r]];j<=y[fk[r]];j++){
                        xl[j]=tp[fk[r]];
                    }
                }
                for(int j=x[fk[r]];j<=r;j++){
                    ans[fk[r]]-=xl[j];
                    xl[j]=s;
                    ans[fk[r]]+=xl[j];
                }
                maxx[fk[r]]=minn[fk[r]]=s;
                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]]=xl[r];
                }
                else{
                    tp[fk[r]]=-1;
                }
            }
            for(int j=fk[l]+1;j<fk[r];j++){
                tp[j]=s;
                ans[j]=(y[j]-x[j]+1)*s;
            }
        }
        if(opt==3){
            int cnt=0;
            for(int j=l;j<=min(r,y[fk[l]]);j++){
                if(tp[fk[l]]!=-1){
                    cnt+=tp[fk[l]];
                }
                else{
                    cnt+=xl[j];
                }
            }
            if(fk[l]!=fk[r]){
                for(int j=x[fk[r]];j<=r;j++){
                    if(tp[fk[r]]!=-1){
                        cnt+=tp[fk[r]];
                    }
                    else{
                        cnt+=xl[j];
                    }
                }
            }
            for(int j=fk[l]+1;j<fk[r];j++){
                cnt+=ans[j];
            }
            cout<<cnt<<endl;
        }
    }
    return 0;
}