区间修改与区间查询

运用Lazy-Tag（懒标记）的维护方法

例题：

洛谷P3372：https://www.luogu.org/problemnew/show/P3372

代码：

#include
     
      #include
      
       #include
       
        using namespace std;#define maxn 100007#define ll long longll sum[maxn<<2],add[maxn<<2],a[maxn],n,m;void build(ll l,ll r,ll k)//建树 [l,r]中 编号为k的区间 {    if(l==r)//叶子节点     {        sum[k]=a[l];        return;    }    ll mid=(l+r)>>1;    build(l,mid,k<<1);//左子树     build(mid+1,r,k<<1|1);//右子树     sum[k]=sum[k<<1]+sum[k<<1|1];//更新区间和 }void Add(ll l,ll r,ll v,ll k)//给定区间[l,r]中所有的数加上v {    add[k]+=v;//打标记     sum[k]+=(r-l+1)*v;//维护对应区间和     return;}void pushdown(ll l,ll r,ll mid,ll k)//标记下传 {    if(add[k]==0) return;//如果没有标记 就退出     Add(l,mid,add[k],k<<1);//传给左子树     Add(mid+1,r,add[k],k<<1|1);//传给右子树     add[k]=0;//传完之后清楚标记 }void update(ll x,ll y,ll v,ll l,ll r,ll k)//更新定区间[x,y]中 区间[l,r]第k个区间 {    if(l>=x&&r<=y) return Add(l,r,v,k);//当这个定区间包含区间[l,r] 则更新区间[l,r]的值     ll mid=(l+r)>>1;    pushdown(l,r,mid,k);//标记下传     if(x<=mid) update(x,y,v,l,mid,k<<1);//更新左子树     if(mid
        
         =x&&r<=y) return sum[k];//当这个定区间包含区间[l,r] 返回区间[l,r]的值     ll mid=(l+r)>>1;    ll res=0;    pushdown(l,r,mid,k);//标记下传     if(x<=mid) res+=query(x,y,l,mid,k<<1);//如果左子树还有值 就加上左子树     if(y>mid) res+=query(x,y,mid+1,r,k<<1|1);//同上右子树     return res;//返回值 }int main(){    cin>>n>>m;    for(ll i=1;i<=n;i++) cin>>a[i];    build(1,n,1);//建原树     for(ll i=1;i<=m;i++)    {        ll x,y,z;        cin>>x;        if(x==1)        {            cin>>x>>y>>z;            update(x,y,z,1,n,1);//更新值         }        else        {               cin>>x>>y;            cout<
         
          <
         
        
       
      
     

 例题：

洛谷P3373：https://www.luogu.org/problemnew/show/P3373

代码：

#include
     
      #include
      
       #include
       
        using namespace std;#define maxn 100007#define ll long longll sum[maxn<<2],add[maxn<<2],mul[maxn<<2],a[maxn],n,m,p;void build(ll l,ll r,ll k){    mul[k]=1;//初始化标记     if(l==r)    {        sum[k]=a[l]%p;        mul[k]=1;        return;    }    ll mid=(l+r)>>1;    build(l,mid,k<<1);//左右子树构建     build(mid+1,r,k<<1|1);    sum[k]=(sum[k<<1]+sum[k<<1|1])%p;//维护sum值 }void pushdown(ll l,ll r,ll mid,ll k)//标记下放 {    //先乘后加     if(mul[k]!=1)//当有乘法标记 计算所有的值     {        sum[k<<1]=(sum[k<<1]*mul[k])%p;         sum[k<<1|1]=(sum[k<<1|1]*mul[k])%p;        mul[k<<1]=(mul[k<<1]*mul[k])%p;        mul[k<<1|1]=(mul[k<<1|1]*mul[k])%p;              add[k<<1]=(add[k<<1]*mul[k])%p;//加法标记也要乘         add[k<<1|1]=(add[k<<1|1]*mul[k])%p;        mul[k]=1;//清除标记     }    if(add[k])//当有加法标记     {        sum[k<<1]=(sum[k<<1]+add[k]*(mid-l+1)%p)%p;//左右子树计算 右子树不用+1         sum[k<<1|1]=(sum[k<<1|1]+add[k]*(r-mid)%p)%p;//注意这里要先算sum 再算add        add[k<<1]=(add[k]+add[k<<1])%p;//如果先算add 那再sum中的add值已经改变         add[k<<1|1]=(add[k]+add[k<<1|1])%p;//坑了我一个晚上（太弱了）        add[k]=0;//清除标记     }    return;}void update1(ll x,ll y,ll v,ll l,ll r,ll k)//在定区间[x,y]加上v {    if(l>=x&&r<=y)//如果整个区间包含     {        add[k]=(add[k]+v)%p;        sum[k]=(sum[k]+(r-l+1)*v)%p;        return;    }    ll mid=(l+r)>>1;    pushdown(l,r,mid,k);    if(x<=mid) update1(x,y,v,l,mid,k<<1);    if(mid
        
         =x&&r<=y)//如果整个区间包含     {        mul[k]=(mul[k]*v)%p;        add[k]=(add[k]*v)%p;        sum[k]=(sum[k]*v)%p;        return;    }    ll mid=(l+r)>>1;    pushdown(l,r,mid,k);    if(x<=mid) update2(x,y,v,l,mid,k<<1);    if(mid
         
          =x&&r<=y) return sum[k]%p;    ll mid=(l+r)>>1;    ll res=0;    pushdown(l,r,mid,k);//标记下放     if(x<=mid) res+=query(x,y,l,mid,k<<1);    res%=p;    if(y>mid) res+=query(x,y,mid+1,r,k<<1|1);    return res%p;}int main(){    cin>>n>>m>>p;    for(ll i=1;i<=n;i++) cin>>a[i];    build(1,n,1);    for(ll i=1;i<=m;i++)    {        ll x,y,z;        cin>>x;        if(x==1)        {            cin>>x>>y>>z;            update2(x,y,z,1,n,1);        }        else if(x==2)        {            cin>>x>>y>>z;            update1(x,y,z,1,n,1);        }        else if(x==3)        {               cin>>x>>y;            cout<
          
           <