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

· · 题解

弱弱的萌新不会用读入优化只好老老实实scanf。。。

进入正题：（以下内容均在sgt结构体内）

此题相对于模板一，加了个区间乘，于是在模板一的基础上需要多开个数组（记录乘法懒标记）、多写个函数（区间乘），还有要把懒标记下放函数做些修改。

变量定义：

sum[]：线段树节点对应区间的元素总和；

addv[]：线段树节点对应区间的所有元素待加的值（懒标记），初值全部设为0；

mulv[]：线段树节点对应区间的所有元素待乘的值（懒标记），初值全部设为1。

过程说明：

建树（Build）：

同模板一。。。

懒标记下放（Push_down）：

原理解释：

1.当对某区间执行加法操作时，由于加法优先级低，不会对乘法操作产生影响，故直接相加即可；

2.当对某区间执行乘法操作时，由于乘法优先级高，会对之前的加法操作产生影响，故需要在相乘时不仅对sum和mulv相乘，也需要对addv相乘；

3.由于上述原因，故需要先算乘法再算加法。

细节实现：

1.子树的sum、mulv、addv值分别乘上当前节点的mulv值；

2.当前节点的mulv值还原，即置为1；

3.子树的addv值加上当前节点的addv值；

4.子树的sum值加上（子树包含元素数量*当前节点的addv值）；

5.当前节点的addv值还原，即置为0。

特别说明：

1.使用前判断，若当前节点的懒标记为空则不需执行此下放函数。虽然执行了也不会有影响，但浪费时间；

2.为尽量节省时间，要将判断放在此函数外而不是函数内。

区间加（Addall）：

同模板一。。。

区间乘（Mulall）：

若当前节点完全包含在待更新区间内，则直接修改当前节点的mulv、addv、sum值即可（参考下放函数说明）；

否则执行与区间加类似的操作即可。

区间查询（Query）：

同模板一。。。

提示：不要忘记取模。。。

代码如下：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
using namespace std;
long long c[500010];
long long p;
struct sgt{
    long long sum[2000010];
    long long addv[2000010];
    long long mulv[2000010];
    void build(int o,int l,int r){
        addv[o]=0;
        mulv[o]=1;
        if(l==r)sum[o]=c[l];
        else{
            int mid=(l+r)>>1;
            int lson=o<<1;
            int rson=lson|1;
            build(lson,l,mid);
            build(rson,mid+1,r);
            sum[o]=(sum[lson]+sum[rson])%p;
        }
    }    
    void push_down(int o,int l,int r,int mid,int lson,int rson){
        mulv[lson]=(mulv[lson]*mulv[o])%p;
        mulv[rson]=(mulv[rson]*mulv[o])%p;
        addv[lson]=(addv[lson]*mulv[o])%p;
        addv[rson]=(addv[rson]*mulv[o])%p;
        sum[lson]=(sum[lson]*mulv[o])%p;
        sum[rson]=(sum[rson]*mulv[o])%p;
        mulv[o]=1;
        addv[lson]=(addv[lson]+addv[o])%p;
        addv[rson]=(addv[rson]+addv[o])%p;
        sum[lson]=(sum[lson]+(mid-l+1)*addv[o])%p;
        sum[rson]=(sum[rson]+(r-mid)*addv[o])%p;
        addv[o]=0;
    }
    void addall(int o,int l,int r,int a,int b,int x){
        if(l>=a && r<=b){
            addv[o]=(addv[o]+x)%p;
            sum[o]=(sum[o]+(r-l+1)*x)%p;
            return;
        }
        else{
            int mid=(l+r)>>1;
            int lson=o<<1;
            int rson=lson|1;
            if(mulv[o]!=1 || addv[o])push_down(o,l,r,mid,lson,rson);
            if(a<=mid)addall(lson,l,mid,a,b,x);
            if(b>mid)addall(rson,mid+1,r,a,b,x);
            sum[o]=(sum[lson]+sum[rson])%p;
        }
    }
    void mulall(int o,int l,int r,int a,int b,int x){
        if(l>=a && r<=b){
            mulv[o]=(mulv[o]*x)%p;
            addv[o]=(addv[o]*x)%p;
            sum[o]=(sum[o]*x)%p;
            return;
        }
        else{
            int mid=(l+r)>>1;
            int lson=o<<1;
            int rson=lson|1;
            if(mulv[o]!=1 || addv[o])push_down(o,l,r,mid,lson,rson);
            if(a<=mid)mulall(lson,l,mid,a,b,x);
            if(b>mid)mulall(rson,mid+1,r,a,b,x);
            sum[o]=(sum[lson]+sum[rson])%p;
        }
    }
    long long query(int o,int l,int r,int a,int b){
        if(l>=a && r<=b)return sum[o]%p;
        else{
            int mid=(l+r)>>1;
            int lson=o<<1;
            int rson=lson|1;
            long long ans=0;
            if(mulv[o]!=1 || addv[o])push_down(o,l,r,mid,lson,rson);
            if(a<=mid)ans+=query(lson,l,mid,a,b);
            if(b>mid)ans+=query(rson,mid+1,r,a,b);
            return ans%p;
        }
    }
};
sgt tree;
int n,m,i,f;
int x,y;
long long k;
int main(){
    scanf("%d%d%d",&n,&m,&p);
    for(i=1;i<=n;i++)scanf("%d",&c[i]);
    tree.build(1,1,n);
    for(i=1;i<=m;i++){
        scanf("%d",&f);
        switch(f){
            case 1:{
                scanf("%d%d%d",&x,&y,&k);
                tree.mulall(1,1,n,x,y,k);
                break;
            }
            case 2:{
                scanf("%d%d%d",&x,&y,&k);
                tree.addall(1,1,n,x,y,k);
                break;
            }
            case 3:{
                scanf("%d%d",&x,&y);
                printf("%lld\n",tree.query(1,1,n,x,y));
                break;
            }    
        }
    }
    return 0;
}