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

· · 题解

一个线段树模板题

重点在如何处理乘法，稍不注意就会出现错误

乘法的操作近似于加法，单个剖析出来乘法仅仅是不用知道区间长度
可是两个在一起的时候就要将要加的值乘一遍

记得开long long，原本我以为不像线段树1要开long long，要记得modp

code：

#include <iostream>
#define ll long long
#define pushup(pos) tree[pos]=(tree[pos<<1]+tree[pos<<1|1])%p
using namespace std;
ll tree[100000<<2],add[100000<<2],mul[100000<<2],p;
int n,m;
void pushdown1(int pos){//乘法下推
    mul[pos<<1]=(mul[pos<<1]*mul[pos])%p;mul[pos<<1|1]=(mul[pos<<1|1]*mul[pos])%p;//乘法相乘
    add[pos<<1]=(add[pos<<1]*mul[pos])%p;add[pos<<1|1]=(add[pos<<1|1]*mul[pos])%p;//加法相乘
    tree[pos<<1]=(tree[pos<<1]*mul[pos])%p;tree[pos<<1|1]=(tree[pos<<1|1]*mul[pos])%p;//值相乘
    mul[pos]=1;//清1（这里不是0，不然倍数都变0了）
}
void pushdown2(int ls,int rs,int pos){//加法下推
    add[pos<<1]=(add[pos<<1]+add[pos])%p;add[pos<<1|1]=(add[pos<<1|1]+add[pos])%p;//加法相加
    tree[pos<<1]=(tree[pos<<1]+add[pos]*ls)%p;tree[pos<<1|1]=(tree[pos<<1|1]+add[pos]*rs)%p;//值相加
    add[pos]=0;//加法清0
}
void build(int l,int r,int pos){//建树
    if(l==r) {cin>>tree[pos];tree[pos]%=p;return;}
    int mid=(l+r)>>1;
    build(l,mid,pos<<1);build(mid+1,r,pos<<1|1);
    pushup(pos);
}
void update1(int L,int R,int l,int r,ll k,int pos){//乘法
    if(l>=L&&r<=R) {tree[pos]=(tree[pos]*k)%p;mul[pos]=(mul[pos]*k)%p;add[pos]=(add[pos]*k)%p;return;}
    int mid=(l+r)>>1;
    pushdown1(pos);pushdown2(mid-l+1,r-mid,pos);
    if(L<=mid) update1(L,R,l,mid,k,pos<<1);
    if(R>mid) update1(L,R,mid+1,r,k,pos<<1|1);
    pushup(pos);
}
void update2(int L,int R,int l,int r,ll k,int pos){//加法
    if(l>=L&&r<=R) {tree[pos]=(tree[pos]+k*(r-l+1))%p;add[pos]=(add[pos]+k)%p;return;}
    int mid=(l+r)>>1;
    pushdown1(pos);pushdown2(mid-l+1,r-mid,pos);
    if(L<=mid) update2(L,R,l,mid,k,pos<<1);
    if(R>mid) update2(L,R,mid+1,r,k,pos<<1|1);
    pushup(pos);
}
ll query(int L,int R,int l,int r,int pos){//求和
    if(l>=L&&r<=R) return tree[pos];
    int mid=(l+r)>>1;
    pushdown1(pos);pushdown2(mid-l+1,r-mid,pos);
    return ((mid>=L?query(L,R,l,mid,pos<<1):0)+(R>mid?query(L,R,mid+1,r,pos<<1|1):0))%p;
}
int main(){
    for(register int i=1;i<100000<<2;i++) mul[i]=1;//清1
    cin>>n>>m>>p;
    build(1,n,1);
    while(m--)
    {
        int t,l,r;
        ll k;
        cin>>t>>l>>r;
        if(t==1) {cin>>k;k%=p;update1(l,r,1,n,k,1);}
        else if(t==2) {cin>>k;k%=p;update2(l,r,1,n,k,1);}
        else cout<<query(l,r,1,n,1)<<endl;
    }
    return 0;
}

管理员大大，我觉得这题可以拓展个xx区间相乘的积