题解 P3373 【【模板】线段树 2】

· · 题解

线段树多个lazy标记的应用。

每个点上的标记表示自己儿子要乘或加上多少。

标记下放时，儿子节点的add标记先乘上父亲节点的乘标记再加上父亲节点的加标记（因为父亲节点的加标记已经乘上了一些乘标记了，不需要再乘一次）

儿子节点的值同上。

儿子节点的乘标记直接乘上父亲节点的乘标记。

修改值的时候要根据下放标记与修改值的先后次序进行微调。

就是这样。

（你拷贝代码会WA的）

#include<bits/stdc++.h>
using namespace std;
struct xds{
    int l,r;
    long long val,add,time;
};
int n,m,p,i,opt,x,y,k,ans;
long long a[100001];
xds t[400001];
void make(int l,int r,int k){
    t[k].time=1;
    t[k].l=l;
    t[k].r=r;
    if (l==r){
        t[k].val=a[l];
        return;
    }
    int mid=(l+r)/2;
    make(l,mid,k*2);
    make(mid+1,r,k*2+1);
    t[k].val=(t[k*2].val+t[k*2+1].val)%p;
}
void down(int k){
    if (t[k].l<t[k].r){
        t[k*2].add=(t[k*2].add*t[k].time+t[k].add)%p;
        t[k*2+1].add=(t[k*2+1].add*t[k].time+t[k].add)%p;
        t[k*2].time=(t[k*2].time*t[k].time)%p;
        t[k*2+1].time=(t[k*2+1].time*t[k].time)%p;
        t[k*2].val=(t[k*2].val*t[k].time+t[k].add*(t[k*2].r-t[k*2].l+1))%p;
        t[k*2+1].val=(t[k*2+1].val*t[k].time+t[k].add*(t[k*2+1].r-t[k*2+1].l+1))%p;
    }
    t[k].add=0;
    t[k].time=1;
}
void ch_a(int k,int a){
    if (t[k].r<x||t[k].l>y) return;
    if (t[k].l>=x&&t[k].r<=y){
        t[k].add=(t[k].add+a)%p;
        t[k].val=(t[k].val+a*(t[k].r-t[k].l-1))%p;
        return;
    }
    if (t[k].add!=0||t[k].time!=1) down(k);
    ch_t(k*2,a);
    ch_t(k*2+1,a);
    t[k].val=(t[k*2].val+t[k*2+1].val)%p;
}
void ch_t(int k,int a){
    if (t[k].r<x||t[k].l>y) return;
    if (t[k].l>=x&&t[k].r<=y){
        t[k].time=(t[k].time*a)%p;
        t[k].add=(t[k].add*a)%p;
        t[k].val=(t[k].val*a)%p;
        return;
    }
    if (t[k].add!=0||t[k].time!=1) down(k);
    ch_t(k*2,a);
    ch_t(k*2+1,a);
    t[k].val=(t[k*2].val+t[k*2+1].val)%p;
}
void ask(int k){
    if (t[k].r<x||t[k].l>y) return;
    if (t[k].l>=x&&t[k].r<=y){
        ans=(ans+t[k].val)%p;
        return;
    }
    if (t[k].add!=0||t[k].time!=1) down(k);
    ask(k*2);
    ask(k*2+1);
}
int main(){
    scanf("%d%d%d",&n,&m,&p);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    make(1,n,1);
    for (i=1;i<=m;i++){
        scanf("%d%d%d",&opt,&x,&y);
        switch (opt){
            case 1:{
                scanf("%d",&k);
                ch_t(1,k%p);
                break;
            }
            case 2:{
                scanf("%d",&k);
                ch_a(1,k%p);
                break;
            }
            case 3:{
                ans=0;
                ask(1);
                printf("%d\n",ans);
                break;
            }
        }
    }
    return 0;
}