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

· · 题解

本题的抄题解现象非常严重，因为我确实看到过不少线段树模板都默不出来的人AC了这道题，而本题的难度显然是要高上不少的

和线段树1一样，不过建议处理一个len，表示区间长度，这样pushdown的时候写起来舒服。另外，本题需要两个lazy，乘lazy一开始是1

这个操作与乘显然没有关系，只要找到指定区间打个lazy，其他区间直接更新值就行了

这个操作也很简单，和线段树1一样，不多讲

毒瘤操作，看一眼就知道要下传区间和，两个lazy

区间和:

本来这个区间的值是正确的，但是没有进行父节点的两个操作，所以就是：

tree[ls].val = tree[ls].val * tree[rt].lazy[0] + tree[rt].lazy[1] * tree[ls].len tree[rs].val = tree[rs].val * tree[rt].lazy[0] + tree[rt].lazy[1] * tree[rs].len 注意加是要乘上长度的，这里最容易错 **乘法lazy** 本来这个区间的乘lazy是正确的，但是没有进行过父节点的乘，所以： $tree[ls].lazy[0] = tree[ls].lazy[0] * tree[rt].lazy[0] tree[rs].lazy[0] = tree[rs].lazy[0] * tree[rt].lazy[0]

加法lazy

本来这个区间的加lazy是正确的，但是没有进行过父节点的乘和加：

tree[ls].lazy[1] = tree[ls].lazy[1] * tree[rt].lazy[0] + tree[rt].lazy[1] tree[rs].lazy[1] = tree[rs].lazy[1] * tree[rt].lazy[0] + tree[rt].lazy[1]

略加思考，显然是没有办法在不完全包含[x,y]（即应该修改的区间)的时候计算出这个区间乘完之后的值，只能修改完左右区间pushup，这样就需要左右子区间的值，所以还要pushdown

这里推荐在打lazy前pushdown，这样lazy是唯一的，不用多考虑

应该修改的区间值直接乘k，不用乘长度

然后结束了，本题大常数线段树也可以过，不用卡常

#include <cstdio>
#define ll long long
#define ls (rt * 2)
#define rs (rt * 2 + 1)
int n,m,p;

struct node{
    int len;
    ll val,lazy[2];
}tree[800005];

void pushup(int rt){
    tree[rt].val = (tree[ls].val + tree[rs].val) % p;
}

void pushdown(int rt){
    tree[ls].lazy[0] = (tree[ls].lazy[0] * tree[rt].lazy[0]) % p;
    tree[rs].lazy[0] = (tree[rs].lazy[0] * tree[rt].lazy[0]) % p;

    tree[ls].lazy[1] = (tree[ls].lazy[1] * tree[rt].lazy[0] + tree[rt].lazy[1]) % p;
    tree[rs].lazy[1] = (tree[rs].lazy[1] * tree[rt].lazy[0] + tree[rt].lazy[1]) % p;

    tree[ls].val = (tree[ls].val * tree[rt].lazy[0] + tree[rt].lazy[1] * tree[ls].len) % p;
    tree[rs].val = (tree[rs].val * tree[rt].lazy[0] + tree[rt].lazy[1] * tree[rs].len) % p;

    tree[rt].lazy[0] = 1;
    tree[rt].lazy[1] = 0;
}

void build(int rt,int l,int r){
    tree[rt].len = r - l + 1;
    tree[rt].lazy[0] = 1;
    tree[rt].lazy[1] = 0;
    if(l == r){
        scanf("%lld",&tree[rt].val);
        return;
    }
    int mid = l + r >> 1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(rt);
}

void upload(int rt,int l,int r,int L,int R,int C){
    pushdown(rt);
    if(l == L && r == R){
        tree[rt].val = (tree[rt].val * C) % p;
        tree[rt].lazy[0] = C;
        return;
    }
    int mid = l + r >> 1;
    if(R <= mid){
        upload(ls,l,mid,L,R,C);
    }else if(L > mid){
        upload(rs,mid+1,r,L,R,C);
    }else{
        upload(ls,l,mid,L,mid,C);
        upload(rs,mid+1,r,mid+1,R,C);
    }
    pushup(rt);
}

void slove(int rt,int l,int r,int L,int R,int C){
    pushdown(rt);
    if(l == L && r == R){
        tree[rt].val = (tree[rt].val + C * tree[rt].len) % p;
        tree[rt].lazy[1] = C;
        return;
    }
    int mid = l + r >> 1;
    if(R <= mid){
        slove(ls,l,mid,L,R,C);
    }else if(L > mid){
        slove(rs,mid+1,r,L,R,C);
    }else{
        slove(ls,l,mid,L,mid,C);
        slove(rs,mid+1,r,mid+1,R,C);
    }
    pushup(rt);
}

int query(int rt,int l,int r,int L,int R){
    pushdown(rt);
    if(l == L && r == R){
        return tree[rt].val;
    }   
    int mid = l + r >> 1;
    if(R <= mid){
        return query(ls,l,mid,L,R);
    }else if(L > mid){
        return query(rs,mid+1,r,L,R);
    }else{
        return (query(ls,l,mid,L,mid) + query(rs,mid+1,r,mid+1,R)) % p;
    }
}

int main(){
    scanf("%d%d",&n,&p);
    build(1,1,n);
    scanf("%d",&m);
    int opt,x,y;
    ll k;
    for(int i = 1;i <= m;i++){
        scanf("%d%d%d",&opt,&x,&y);
        if(opt == 1){
            scanf("%lld",&k);
            upload(1,1,n,x,y,k % p);
        }else if(opt == 2){
            scanf("%lld",&k);
            slove(1,1,n,x,y,k % p);
        }else{
            printf("%d\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

解释一下为什么开8倍：因为这样pushdown可能会push到神秘空间（长度为0的区间），不影响结果，但是会RE，所以再开两倍

本人很懒，所以加法是从乘法改的，用了大常数写法