题解：P10148 [Ynoi1999] M47升级型“钢铁阿诺”

cuijiexiong · 2026-07-24 16:26:16 · 题解

~emm，题意区间加值，区间查询，这不莫队二离吗。（写完代码），wc，™是区间改值~。

这提醒我们要认真审题。~成奶龙了~。

题意，一定要认真审题！！！

分析

本题有三个维度，分别是整数序列 a_1,\cdots,a_n、操作序列（修改整数序列，和查询整数序列）、询问（这里‘询问’是特指的）。（这里定义好，方便下面理解）

我们选择对操作序列进行扫描线，试图从左往右枚举右端点 R，计算所有左端点 L\le R 的所有答案 ans_L，即 ans_i 表示区间 [i,R] 的答案。

对于每个询问就可以离线下来，我们用 Ans_i 表示第 i 个询问的答案。

我们对整数序列这一维进行分块。

现在假设我们已经知道右端点 R=k 时，ans_1 到 ans_k 的值，试图移动 R 到 R=k+1，看看能不能维护新的 ans_1 到 ans_{k+1} 的值。

• 现在来的操作是查询 [l,r]：

  • 对于散块，我们可以知道散块各个位置是什么值，什么时候覆盖的，这样我们就可以对 ans 对应的前缀进行更新这散块的贡献。
    具体地，枚举散块的所有位置 i，获得该位置的值 a_i 和最近被覆盖的时间 t_i，对 ans_1,\cdots,ans_{t_i} 都加上 a_i（使用数据结构快速维护）。

  • 对于整块，这块的值都是一样的，和上面是类似的。

  • 对于整块，这块的值是不一样的……似乎很难更新 ans 了，那我们就干脆先维护一个不完整的 ans，后面再试图弥补（不操作）。

• 现在来的操作是修改：

  • 对于整块直接打懒标记（上面查询散块记得下传）。

  • 对于散块直接维护。

更新所有 Ans，虽然我们记录的是不完整的答案。

现在我们尝试弥补散块修改对整块查询的贡献。

• for 枚举第 i 块。

  • for 枚举操作序列维度，即执行到第 j 个操作。

  我们维护两个值：

  一个散块修改可以被表示成 [l,r,x] 表示把 l 到 r 区间的值都变为 x。

  我们先考虑对于一个位置上的修改。

  如果位置 k 在被第 j 次执行的散块修改后，在第 R 次操作之前没被其他操作覆盖，且 L\le j，那么对于一个询问 [L,R] 的贡献就为

  (Q_R-Q_{j-1})\times D_{j,k}

  为了方便我们操作，我们维护两个数组（使用分块进行 O(\sqrt n) 修改，O(1) 查询）

  修改时

  当我们在第 j 次操作把第 k 位修改成 D_{j,k}：

  它对所有 L \in [1, j] 都有影响。
  所以我们在 f 的 [1, j] 区间上加上 D_{j,k}。
  在 g 的 [1, j] 区间上加上 D_{j,k} \times Q_{j-1}。

  被覆盖时

  当这个第 k 个值被后续覆盖掉时，我们执行相反的操作：

  对 f 的区间 [1,old] 加 -D_{old,k}。
  对 g 的区间 [1,old] 加 -D_{old,k}\times Q_{j}。
  其中 old 为它上次被修改时的操作编号。

  这样，f 和 g 就实时维护了所有有效修改的分布。

  颜色段均摊优化

  但是，如果来一个散块就直接把它影响的元素一个一个地修改，对 f 和 g 的操作数量就达到了 O(n\sqrt n) 级别了。我们选择使用颜色段均摊，对连续的区间只进行一次修改，这样对 f 和 g 的操作次数就均摊到 O(n) 了。

  对于整块修改的处理

  当该块被整块修改覆盖时，我们不做操作和贡献，但整块性被破坏时，我们就可以把剩下整块修改元素当成散块事件维护。

  来一个询问 [L,R] 时该怎么做？
  对询问的 Ans 加上 Q_R\times f_L - g_L 即可。

注意要选择合适的数据结构来平衡时间复杂度。

这就做完了…… :::error[卡不过去的代码www]

#include<bits/stdc++.h>
#define fi first
#define se second
#define pi pair<int,int>
typedef long long ll; 
using namespace std;
const int Shift=10;
const int B=(1<<Shift);
const int N=5e5+10000;
char buf[1<<20],*buf1,*buf2;
#define gc() (buf1==buf2&&(buf2=(buf1=buf)+fread(buf,1,1<<20,stdin)),*buf1++)
inline ll rd(){
    char c=gc();ll f=1,res=0;
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=gc();
    }
    while(c>='0'&&c<='9'){
        res=res*10+c-'0';
        c=gc();
    }
    return res*f;
}
char out[30*N];
int op;
inline void wt(ll x)
{
    if(x==0) out[op++]='0';
    else{
        char s[20];
        int n=0;
        while(x)
            s[n++]=x%10+'0',x/=10;
        while(n)
            out[op++]=s[--n];
    }
    out[op++]='\n';
}
int n,m,q,bk,mbk;
struct done{
    int op,l,r,v;
};
struct node{
    int l,r,id;
};
done a[N];
node qu[N];
int qutp;
ll Ans[N];
struct color{
    int l; pi v;
};
pi col[N];
color rub[N];
int rubtp;
int Q=0;
struct Sqrt_one_to_sqrt{
    ll sum0[N],sum1[500];
    inline void add(int x,ll s){
        int id=(x>>Shift);
        sum0[x]+=s;
        sum1[id]+=s;
    }
    inline ll ask(int x){
        int id=(x>>Shift);
        ll res=0;
        for(int i=x;i<(id<<Shift)+B;i++) res+=sum0[i];
        for(int i=id+1;i<=bk;i++) res+=sum1[i];
        return res;  
    }
}ans;
struct Sqrt_sqrt_to_one{
    ll sum1[2][N],sum2[2][500];
    inline void add(int x,ll s){
        int id=(x>>Shift);
        for(int i=(id<<Shift);i<=x;i++) sum1[0][i]+=s,sum1[1][i]+=s*Q;
        for(int i=0;i<id;i++) sum2[0][i]+=s,sum2[1][i]+=s*Q;
    }
    inline ll ask(int x){
        return (sum1[0][x]+sum2[0][x>>Shift])*Q-(sum1[1][x]+sum2[1][x>>Shift]);
    }
    inline void clear(){
        memset(sum1,0,sizeof sum1);
        memset(sum2,0,sizeof sum2);
        for(int i=0;i<=m;i++) sum1[0][i]=sum1[1][i]=0;
        for(int i=0;i<=mbk;i++) sum2[0][i]=sum2[1][i]=0;
    }
}f;
struct Sqrt_special{
    int val_fi[N],val_se[N],tag_fi[500],tag_se[500];
    bool vis[N];
    inline void add(int l,int r,pi s){
        int L=(l>>Shift),R=(r>>Shift);
        if(L==R){
            if(vis[L]){
                for(int i=(L<<Shift);i<(R<<Shift)+B;i++)
                    val_fi[i]=tag_fi[L],val_se[i]=tag_se[L];
                vis[L]=false;
            }
            for(int i=l;i<=r;i++) val_fi[i]=s.fi,val_se[i]=s.se;
        }else{
            if(vis[L]){
                for(int i=(L<<Shift);i<(L<<Shift)+B;i++)
                    val_fi[i]=tag_fi[L],val_se[i]=tag_se[L];
                vis[L]=false;
            }
            if(vis[R]){
                for(int i=(R<<Shift);i<(R<<Shift)+B;i++)
                    val_fi[i]=tag_fi[R],val_se[i]=tag_se[R];
                vis[R]=false;
            }
            for(int i=l;i<(L<<Shift)+B;i++) val_fi[i]=s.fi,val_se[i]=s.se;
            for(int i=(R<<Shift);i<=r;i++) val_fi[i]=s.fi,val_se[i]=s.se;
            for(int i=L+1;i<=R-1;i++)
                tag_fi[i]=s.fi,tag_se[i]=s.se,vis[i]=true;
        }
    }
    inline pi ask(int x){
        int id=(x>>Shift);
        if(vis[id]) return {tag_fi[id],tag_se[id]};
        return {val_fi[x],val_se[x]};
    }
    inline pi bask(int id){
        return {tag_fi[id],tag_se[id]};
    }
}spc;
inline void query(int l,int r){
    int L=(l>>Shift),R=(r>>Shift);
    if(L==R){
        for(int i=l;i<=r;i++){
            pi it=spc.ask(i);
            ans.add(it.se,it.fi);
        }
    }else{
        for(int i=l;i<=(L<<Shift)+B-1;i++){
            pi it=spc.ask(i);
            ans.add(it.se,it.fi);
        }
        for(int i=(R<<Shift);i<=r;i++){
            pi it=spc.ask(i);
            ans.add(it.se,it.fi);
        }
        for(int i=L+1;i<=R-1;i++)
            if(spc.vis[i]){
                pi it=spc.bask(i);
                ans.add(it.se,(it.fi<<Shift));
            }
    }
}
inline void modify(int l,int r,int s){
    rubtp=0;
    int last=l;
    for(int i=l+1;i<=r;i++)
        if(col[i].fi!=col[i-1].fi||col[i].se!=col[i-1].se)
            rub[++rubtp]={last,col[last]},last=i;
    rub[++rubtp]={last,col[last]};
    rub[++rubtp]={r+1,{0,0}};
    for(int i=1;i<rubtp;i++){
        auto &it=rub[i];
        f.add(it.v.fi,1ll*s*(rub[i+1].l-it.l)*it.v.se);
    }
}
int main(){
    n=rd(),m=rd(),q=rd();
    bk=(n>>Shift)+1;
    mbk=(m>>Shift)+1;
//  cout<<B<<"\n";
    for(int i=1;i<=m;i++){
        a[i].op=rd();
        a[i].l=rd(),a[i].r=rd();
        if(a[i].op==1) a[i].v=rd();
    }
    for(int i=1;i<=q;i++){
        qu[i]={rd(),rd(),i};
    }
    sort(qu+1,qu+1+q,[](node x,node y){
        return x.r<y.r;
    });
    qutp=1;
    for(int i=1;i<=m;i++){
        if(a[i].op==1){
            spc.add(a[i].l,a[i].r,{a[i].v,i});
        }else{
            query(a[i].l,a[i].r);
        }
        while(qu[qutp].r==i){
            Ans[qu[qutp].id]+=ans.ask(qu[qutp].l);
            qutp++;
        }
    }
    for(int i=0;i<=n;i+=B){
        int l=i,r=i+B-1;
        bool tvis=false;
        pi tag;
        Q=0;
        f.clear();
        qutp=1;
        for(int j=1;j<=m;j++){
            if(!(a[j].l>r||a[j].r<l)){
                if(a[j].op==1){
                    if(a[j].l<l&&r<a[j].r){ //整块覆盖 
                        tag={j,a[j].v};
                        if(!tvis) modify(l,r,-1);
                        tvis=true;
                    }else{
                        int el=max(l,a[j].l),er=min(r,a[j].r);
                        if(tvis){
                            tvis=false;
                            for(int k=l;k<=r;k++) col[k]=tag;
                            for(int k=el;k<=er;k++) col[k]={j,a[j].v};
                            modify(l,r,1);
                        }else{
                            modify(el,er,-1);
                            for(int k=el;k<=er;k++) col[k]={j,a[j].v};
                            modify(el,er,1);
                        }
                    }
                }else Q+=(a[j].l<l&&r<a[j].r);
            }
            while(qu[qutp].r==j){
                Ans[qu[qutp].id]+=f.ask(qu[qutp].l);
                qutp++;
            }
        }
    }
    for(int i=1;i<=q;i++) wt(Ans[i]);
    fwrite(out,1,op,stdout);
    return 0;
}

::: :::success[upd:卡过去了，加强版也可以！]

//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define fi first
#define se second
#define pi pair<int,int>
typedef long long ll; 
using namespace std;
const int N=5e5+10000;
const short W=11;
const int B=2048;
int n,m,q,bk,mbk;
struct done{
    int op,l,r,v;
};
struct node{
    int l,r,id;
};
done a[N];
node qu[N];
int qutp;
ll Ans[N];
pi col[N];
int rub[N];
int rubtp;
int Q=0;
struct Sqrt_one_to_sqrt{
    ll sum[2][N];
    inline __attribute__((always_inline)) void add(int x,ll s){
        int id=(x>>W);
        sum[0][x]+=s;
        sum[1][id]+=s;
    }
    inline __attribute__((always_inline)) ll ask(int x){
        int id=(x>>W);
        ll res=0;
        for(int i=x;i<(id<<W)+B;i++) res+=sum[0][i];
        for(int i=id+1;i<=bk;i++) res+=sum[1][i];
        return res;  
    }
}ans;
bool pass[N];
ll fsum10[N],fsum11[N],fsum20[500][500],fsum21[500][500];
bool ftf=true;
int now=0;
inline __attribute__((always_inline)) void fadd(int x,ll s){
    if(s==0) return ;
    ftf=false;
    int id=(x>>W);
    ll tmp=s*Q;
    for(int i=(id<<W);i<=x;i++) fsum10[i]+=s,fsum11[i]+=tmp;
    for(int i=0;i<id;i++) fsum20[now][i]+=s,fsum21[now][i]+=tmp;
}
inline __attribute__((always_inline)) ll fask(int x){
    return (fsum10[x]+fsum20[now][x>>W])*Q-(fsum11[x]+fsum21[now][x>>W]);
}
inline __attribute__((always_inline)) void fclear(){
    if(ftf) return ;
    now++;
    memset(fsum10,0,sizeof fsum10);
    memset(fsum11,0,sizeof fsum11);
    ftf=true;
}
struct Sqrt_special{
    pi val[N],tag[N];
    bool vis[N];
    inline __attribute__((always_inline)) void add(int l,int r,pi s){
        int L=(l>>W),R=(r>>W);
        if(L==R){
            if(vis[L]){
                for(int i=(L<<W);i<(R<<W)+B;i++)
                    val[i]=tag[L];
                vis[L]=false;
            }
            for(int i=l;i<=r;i++) val[i]=s;
        }else{
            int l_=L<<W,r_=R<<W;
            if(vis[L]){
                for(int i=l_;i<l_+B;i++)
                    val[i]=tag[L];
                vis[L]=false;
            }
            if(vis[R]){
                for(int i=r_;i<r_+B;i++)
                    val[i]=tag[R];
                vis[R]=false;
            }
            for(int i=l;i<l_+B;i++) val[i]=s;
            for(int i=r_;i<=r;i++) val[i]=s;
            for(int i=L+1;i<=R-1;i++)
                tag[i]=s,vis[i]=true;
        }
    }
    inline __attribute__((always_inline)) pi ask(int x){
        int id=(x>>W);
        if(vis[id]) return tag[id];
        return val[x];
    }
    inline __attribute__((always_inline)) pi bask(int id){
        return tag[id];
    }
}spc;
inline __attribute__((always_inline)) void query(int l,int r){ 
    int L=(l>>W),R=(r>>W);
    if(L==R){
        for(int i=l;i<=r;i++){
            int id=i>>W;
            pi it=spc.vis[id]?spc.tag[id]:spc.val[i];
            ans.add(it.se,it.fi);
        }
    }else{
        for(int i=l;i<=(L<<W)+B-1;i++){
            int id=i>>W;
            pi it=spc.vis[id]?spc.tag[id]:spc.val[i];
            ans.add(it.se,it.fi);
        }
        for(int i=(R<<W);i<=r;i++){
            int id=i>>W;
            pi it=spc.vis[id]?spc.tag[id]:spc.val[i];
            ans.add(it.se,it.fi);
        }
        for(int i=L+1;i<=R-1;i++)
            if(spc.vis[i]){
                pi it=spc.bask(i);
                ans.add(it.se,(it.fi<<W));
            }
    }
}
inline __attribute__((always_inline)) void modify(int l,int r,int s){
    rubtp=0;
    int last=l; pi tmp=col[l];
    for(int i=l+1;i<=r;i++)
        if(col[i]!=tmp)
            rub[++rubtp]=last,last=i,tmp=col[i];
    rub[++rubtp]=last;
    rub[++rubtp]=r+1;
    for(int i=1;i<rubtp;i++){
        fadd(col[rub[i]].fi,s*(rub[i+1]-rub[i])*col[rub[i]].se);
    }
}
inline __attribute__((always_inline)) bool cmp(const node &x,const node &y){
    return x.r<y.r;
}
char buf[1<<20],*buf1,*buf2;
#define gc() (buf1==buf2&&(buf2=(buf1=buf)+fread(buf,1,1<<20,stdin)),*buf1++)
inline ll rd(){
    char c=gc();ll f=1,res=0;
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=gc();
    }
    while(c>='0'&&c<='9'){
        res=res*10+(c^48);
        c=gc();
    }
    return res*f;
}
char out[30*N];
int op;
inline void wt(ll x)
{
    if(x==0) out[op++]='0';
    else{
        char s[20];
        int n=0;
        while(x)
            s[n++]=x%10+'0',x/=10;
        while(n)
            out[op++]=s[--n];
    }
    out[op++]='\n';
}
int main(){
    n=rd(),m=rd(),q=rd();
    bk=(n>>W)+1;
    mbk=(m>>W)+1;
//  cout<<B<<"\n";
    for(int i=1;i<=m;i++){
        a[i].op=rd();
        a[i].l=rd(),a[i].r=rd();
        if(a[i].op==1) a[i].v=rd();
    }
    for(int i=1;i<=q;i++){
        qu[i]={rd(),rd(),i};
    }
    sort(qu+1,qu+1+q,cmp);
    qutp=1;
    for(int i=1;i<=m;i++){
        if(a[i].op==1){
            spc.add(a[i].l,a[i].r,{a[i].v,i});
            pass[a[i].l>>W]=true;
            pass[a[i].r>>W]=true;
        }else{
            query(a[i].l,a[i].r);
        }
        for(;qu[qutp].r==i;qutp++){
            Ans[qu[qutp].id]+=ans.ask(qu[qutp].l);
        }
    }
    for(int i=0;i<=n;i+=B){
        if(!pass[i>>W]) continue;
        int l=i,r=i+B-1;
        bool tvis=false;
        pi tag;
        Q=0;
        fclear();
        qutp=1;
        for(int j=1;j<=m;j++){
            if(!(a[j].l>r||a[j].r<l)){
                if(a[j].op==1){
                    if(a[j].l<l&&r<a[j].r){ //整块覆盖 
                        tag={j,a[j].v};
                        if(!tvis) modify(l,r,-1);
                        tvis=true;
                    }else{
                        int el=max(l,a[j].l),er=min(r,a[j].r);
                        if(tvis){
                            tvis=false;  
                            for(int k=l;k<=r;k++) col[k]=tag;
                            for(int k=el;k<=er;k++) col[k]={j,a[j].v};
                            modify(l,r,1);
                        }else{
                            modify(el,er,-1);
                            for(int k=el;k<=er;k++) col[k]={j,a[j].v};
                            modify(el,er,1);
                        }
                    }
                }else Q+=(a[j].l<l&&r<a[j].r);
            }
            for(;qu[qutp].r==j;qutp++){
                Ans[qu[qutp].id]+=fask(qu[qutp].l);
            }
        }
    }
    for(int i=1;i<=q;i++) wt(Ans[i]);
    fwrite(out,1,op,stdout);
    return 0;
}

::: 注：选择 C++11，不要开 O2。

鸣谢：@YL_LiLuo_SK，感谢大佬提供卡常帮助，非常非常非常非常感谢！

笨作者花了一天才理解大佬们的题解，又花了一天半卡常，觉得又帮助的能留下点赞安慰一下作者吗qwq。