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

渡海 · 2017-11-02 20:00:41 · 题解

接3372我题解的板子修改，依旧参考will大佬和CSDN：http://www.cnblogs.com/TenosDoIt/p/3453089.html

关于3373，有几个细节要提一下。

1：tag2的初始值为1；

2：pushdown里先tag2后tag1（先乘后加）；

3：对tag2进行push需要先把tag1*tag2，tag2*tag2，val*tag2，最后别忘了tag2=1；

4：tag2不需要乘区间；

下面是code：

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    long long val,lazytag,lazytag2;
}segTree[100000*4+5];
long long a[100005];
long long n,m,t,x,y,k,p;
void build(int root,long long arr[],int istart,int iend){//建树
    segTree[root].lazytag=0;
    segTree[root].lazytag2=1;
    if(istart==iend){
        segTree[root].val=arr[istart];
    }else{
        int mid=(istart+iend)/2;
        build(root*2,arr,istart,mid);
        build(root*2+1,arr,mid+1,iend);
        segTree[root].val=segTree[root*2].val+segTree[root*2+1].val;
    }
}
void pushDown(int root,int start,int end){//插入懒标记
    **if(segTree[root].lazytag2!=1){**
        segTree[root*2].lazytag=(segTree[root*2].lazytag*segTree[root].lazytag2)%p;
        segTree[root*2+1].lazytag=(segTree[root*2+1].lazytag*segTree[root].lazytag2)%p;
        segTree[root*2].lazytag2=(segTree[root*2].lazytag2*segTree[root].lazytag2)%p;
        segTree[root*2+1].lazytag2=(segTree[root*2+1].lazytag2*segTree[root].lazytag2)%p;
        int midd=(end+start)/2;
        segTree[root*2].val=(segTree[root*2].val*(segTree[root].lazytag2))%p;
        segTree[root*2+1].val=(segTree[root*2+1].val*(segTree[root].lazytag2))%p;
        segTree[root].lazytag2=1;
    } 
    if(segTree[root].lazytag!=0){
        segTree[root*2].lazytag+=segTree[root].lazytag;
        segTree[root*2+1].lazytag+=segTree[root].lazytag;
        int mid=(end+start)/2;
        segTree[root*2].val+=segTree[root].lazytag*(mid-start+1);
        segTree[root*2+1].val+=segTree[root].lazytag*(end-mid);
        segTree[root].lazytag=0;
    }
}
long long query(int root,int nstart,int nend,int qstart,int qend){//查询区间
    if(qstart>nend||qend<nstart){
        return 0; 
    }if(qstart<=nstart&&qend>=nend){
        return segTree[root].val;
    }
    pushDown(root,nstart,nend);
    int mid=(nstart+nend)/2;
    return query(root*2,nstart,mid,qstart,qend)+query(root*2+1,mid+1,nend,qstart,qend);
}
void update(int root,int nstart,int nend,int ustart,int uend,int addval){//赋值
    if(ustart>nend||uend<nstart){
        return;
    }if(ustart<=nstart&&uend>=nend){
        segTree[root].lazytag+=addval;
        segTree[root].val+=addval*(nend-nstart+1);
        return;
    }
    pushDown(root,nstart,nend);
    int mid=(nstart+nend)/2;
    update(root*2,nstart,mid,ustart,uend,addval);
    update(root*2+1,mid+1,nend,ustart,uend,addval);
    segTree[root].val=segTree[root*2].val+segTree[root*2+1].val;
}
**void tupdate(int root,int nstart,int nend,int ustart,int uend,int addval){//赋值(chengfa**
    if(ustart>nend||uend<nstart){
        return;
    }if(ustart<=nstart&&uend>=nend){
        segTree[root].lazytag=(segTree[root].lazytag*addval)%p;
        segTree[root].lazytag2=(segTree[root].lazytag2*addval)%p;
        segTree[root].val=(segTree[root].val*addval)%p;
        return;
    }
    pushDown(root,nstart,nend);
    int mid=(nstart+nend)/2;
    tupdate(root*2,nstart,mid,ustart,uend,addval);
    tupdate(root*2+1,mid+1,nend,ustart,uend,addval);
    segTree[root].val=segTree[root*2].val+segTree[root*2+1].val;
}
int main(){
    scanf("%lld%lld%lld",&n,&m,&p);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    build(1,a,1,n);
    for(int i=1;i<=m;i++){
        scanf("%lld",&t);
        if(t==2){
            scanf("%lld%lld%lld",&x,&y,&k);
            update(1,1,n,x,y,k);
        }if(t==3){
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",query(1,1,n,x,y)%p);
        }if(t==1){
            scanf("%lld%lld%lld",&x,&y,&k);
            tupdate(1,1,n,x,y,k);
        }
    }
    return 0;
}