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

背景

这里传标记的顺序会决定答案的正确与否

分析

WA30分的还有很多人是 pushdown 写错了(就是只AC了1 3 4点并且找不到错哪),主要问题应该在于 lazy 和 mul 标记传递的先后顺序。因为先乘再加和先加再乘结果是不一样的,而且都是错的。这可能就会导致WA了很长时间也没有调出来。正确的解决方式应该在每一次下传时把 lazy 标记乘以 mul 标记,然后再传给下一个节点。

代码

然后就没有啥复杂的啦

#include<cstdio>

typedef long long int64;
const int MAXN = 100000 + 6;
int64 MOD,A[MAXN];

class SegmentTree{
    public:int l,r;
    public:int64 sum;
    public:int64 add,mul;
};
SegmentTree t[MAXN * 4];

inline int LEFT(int x){return x << 1;}
inline int RIGHT(int x){return x << 1 | 1;}
inline int MID(int l,int r){return (l + r) >> 1;}

void maintain(int p){
    t[p].sum = (t[LEFT(p)].sum + t[RIGHT(p)].sum) % MOD;
}

void build(int p,int l,int r){
    t[p].l = l;t[p].r = r;
    t[p].add = 0;t[p].mul = 1;
    if(l == r){
        t[p].sum = A[l];
        return;
    }
    build(LEFT(p),l,MID(l,r));
    build(RIGHT(p),MID(l,r) + 1,r);
    maintain(p);
}

inline void spread(int p){
    int64 mid = (t[p].l + t[p].r) >> 1;
    t[LEFT(p)].sum = (t[LEFT(p)].sum * t[p].mul + t[p].add * (mid - t[p].l + 1)) % MOD;
    t[RIGHT(p)].sum = (t[RIGHT(p)].sum * t[p].mul + t[p].add*(t[p].r - mid)) % MOD;
    t[LEFT(p)].mul = (t[LEFT(p)].mul * t[p].mul) % MOD;
    t[RIGHT(p)].mul = (t[RIGHT(p)].mul * t[p].mul) % MOD;
    t[LEFT(p)].add = (t[LEFT(p)].add * t[p].mul + t[p].add) % MOD;
    t[RIGHT(p)].add = (t[RIGHT(p)].add * t[p].mul + t[p].add) % MOD;

    t[p].mul=1;
    t[p].add=0;
}

void changeMul(int p,int l,int r,int64 d){
    if(l <= t[p].l && r >= t[p].r){
        t[p].add = t[p].add * d;
        t[p].mul = t[p].mul * d;
        t[p].sum = t[p].sum * d;
        return;
    }
    spread(p);
    if(l <= MID(t[p].l,t[p].r)){
        changeMul(LEFT(p),l,r,d);
    }
    if(r > MID(t[p].l,t[p].r)){
        changeMul(RIGHT(p),l,r,d);
    }
    maintain(p);
}

void changeAdd(int p,int l,int r,int d){
    if(l <= t[p].l && r >= t[p].r){
        t[p].add = (t[p].add + d);
        t[p].sum = (t[p].sum + d * (t[p].r - t[p].l + 1));
        return;
    }
    spread(p);
    if(l <= MID(t[p].l,t[p].r)){
        changeAdd(LEFT(p),l,r,d);
    }
    if(r > MID(t[p].l,t[p].r)){
        changeAdd(RIGHT(p),l,r,d);
    }
    maintain(p);
}

int64 ask(int p,int l,int r){
    if(l <= t[p].l && r >= t[p].r){
        return t[p].sum;
    }
    spread(p);
    int64 ans = 0;
    if(l <= MID(t[p].l,t[p].r)){
        ans = (ans + ask(LEFT(p),l,r));
    }
    if(r > MID(t[p].l,t[p].r)){
        ans = (ans + ask(RIGHT(p),l,r));
    }
    return ans;
}

int main(){
    int n,m;
    scanf("%d %d %lld",&n,&m,&MOD);

    for(int i = 1;i <= n;i++){
        scanf("%lld",&A[i]);
    }

    build(1,1,n);

    int op,x,y;
    int64 z;
    while(m--){
        scanf("%d %d %d",&op,&x,&y);
        if(op == 1){
            scanf("%lld",&z);
            changeMul(1,x,y,z);
        }else if(op == 2){
            scanf("%lld",&z);
            changeAdd(1,x,y,z);
        }else{
            printf("%d\n",ask(1,x,y) % MOD);
        }
    }

    return 0;
}