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

kgrox · 2017-04-18 12:58:39 · 题解

思路跟楼下dalao公式一样 乘法分配率

记得乘法标签要膜！！！！！否则会爆

非指针代码如下

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#define ls (2*n)
#define rs (2*n+1)
#define mid ((l+r)/2)
#define LL long long
#include<cstring>
#include<stack>
using namespace std;
LL tree[1000000],a[1000000],lazy[1000000],tag[1000000];
LL x,y,k,mod,n,m;
void collect(LL n){tree[n]=tree[ls]+tree[rs];tree[n]%=mod;}
void pushdown(LL n,LL l,LL r)
{
    if(tag[n]!=1)
    {
        tree[ls]*=tag[n];tree[ls]%=mod;
        tree[rs]*=tag[n];tree[rs]%=mod;
        lazy[ls]*=tag[n];lazy[ls]%=mod;
        lazy[rs]*=tag[n];lazy[rs]%=mod;
        tag[ls]*=tag[n];tag[ls]%=mod;
        tag[rs]*=tag[n];tag[rs]%=mod;
        tag[n]=1;
    }
    if(lazy[n]!=0)
    {
        tree[ls]+=lazy[n]*(mid-l+1);tree[ls]%=mod;
        tree[rs]+=lazy[n]*(r-mid);tree[rs]%=mod;
        lazy[ls]+=lazy[n];lazy[ls]%=mod;
        lazy[rs]+=lazy[n];lazy[rs]%=mod;
        lazy[n]=0;
        return;
    }
    return;
}
void build(LL n,LL l,LL r)
{
   tag[n]=1;lazy[n]=0;
   if(l==r){tree[n]=a[l];return;}
   build(ls,l,mid);
   build(rs,mid+1,r);
   collect(n);
}
void multy(LL n,LL l,LL r,LL mul,LL mur,LL x)
{
    //printf("->%lld %lld %lld %lld\n",l,r,mul,mur);
    if(mul==l&&mur==r){lazy[n]*=x;lazy[n]%=mod;tag[n]*=x;tag[n]%=mod;tree[n]*=x;tree[n]%=mod;return;}
    pushdown(n,l,r);
    if(mur<=mid)multy(ls,l,mid,mul,mur,x);
    else if(mul>=mid+1)multy(rs,mid+1,r,mul,mur,x);
    else
    {
        multy(ls,l,mid,mul,mid,x);
        multy(rs,mid+1,r,mid+1,mur,x);
    }
    collect(n);
}
void add(LL n,LL l,LL r,LL addl,LL addr,LL x)
{
    if(addl==l&&addr==r){lazy[n]+=x;lazy[n]%=mod;tree[n]+=(r-l+1)*x;tree[n]%=mod;return;}
    pushdown(n,l,r);
    if(addr<=mid)add(ls,l,mid,addl,addr,x);
    else if(addl>=mid+1)add(rs,mid+1,r,addl,addr,x);
    else
    {
        add(ls,l,mid,addl,mid,x);
        add(rs,mid+1,r,mid+1,addr,x);
    }
    collect(n);
}
LL ask(LL n,LL l,LL r,LL askl,LL askr)
{
    if(askl==l&&askr==r)
    {
        return tree[n];
    }
    pushdown(n,l,r);
    LL res;
    if(askr<=mid)res=ask(ls,l,mid,askl,askr)%mod;
    else if(askl>=mid+1)res=ask(rs,mid+1,r,askl,askr)%mod;
    else
    {
        res=ask(ls,l,mid,askl,mid)%mod+ask(rs,mid+1,r,mid+1,askr)%mod;
    }
    return res%mod;
}
/*void print(LL n,LL l,LL r)
{
    printf("l:%lld r:%lld node:%lld tag:%lld lazy:%lld num:%lld\n",l,r,n,tag[n],lazy[n],tree[n]);
    if(l==r) return;
    print(ls,l,mid);
    print(rs,mid+1,r);
}*/
int main()
{
    cin>>n>>m>>mod;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int tmpa;
        cin>>tmpa;
        if(tmpa==1){cin>>x>>y>>k;multy(1,1,n,x,y,k);}
        else if(tmpa==2){cin>>x>>y>>k;add(1,1,n,x,y,k);}
        else {cin>>x>>y;cout<<ask(1,1,n,x,y)<<endl;}
        //print(1,1,n);
    }
}