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

「QQ红包」 · 2017-06-30 20:30:29 · 题解

线段树的模板题，具体见注释

/* ID: ylx14271

PROG: 线段树2

LANG: C++

*/

#include<set>  
#include<map>  
#include<list>  
#include<queue>  
#include<stack>  
#include<string>  
#include<math.h>  
#include<time.h>  
#include<vector>  
#include<bitset>  
#include<memory>  
#include<utility>  
#include<stdio.h>  
#include<sstream>  
#include<iostream>  
#include<stdlib.h>  
#include<string.h>  
#include<algorithm> 
#define LL unsigned long long  
#define LO long long 
using namespace std;
struct node
{
    long long l,r;//左端点和右端点 
    long long jia;//加 
    long long ch;//乘 
    long long s;
} t[300100];
long long a[300100];
long long n,m,x,y,k,c,i,j;
long long sum,p; //膜数 
void bt(long long l,long long r,long long u)//建树 
{
    t[u].l=l;//左端点 
    t[u].r=r;//右端点 
    t[u].jia=0;
    t[u].ch=1;//初始化 
    if (l==r)//长度为1的区间 
    {
        t[u].s=a[l];
        return;
    }
    bt(l        ,(l+r)/2,u*2);//左子树 
    bt((l+r)/2+1,r      ,u*2+1);//右子树
    t[u].s=(t[u*2].s+t[u*2+1].s)%p;//更新当前结点的值
}
void down(LO x)
{
    t[x*2].jia=(t[x*2].jia*t[x].ch+t[x].jia)%p;//加 
    t[x*2+1].jia=(t[x*2+1].jia*t[x].ch+t[x].jia)%p;
    t[x*2].ch=(t[x*2].ch*t[x].ch)%p;//乘 
    t[x*2+1].ch=(t[x*2+1].ch*t[x].ch)%p;
    t[x*2].s=(t[x].jia*(t[x*2].r-t[x*2].l+1)%p+t[x*2].s*t[x].ch%p)%p;//求和 
    t[x*2+1].s=(t[x].jia*(t[x*2+1].r-t[x*2+1].l+1)%p+t[x*2+1].s*t[x].ch%p)%p;//求和 
    t[x].jia=0;t[x].ch=1; 
}
void cheng(LO l,LO r,LO x,LO d)
{
    if (l<=t[x].l&&t[x].r<=r)//全部包括 

{//三个值全部都要乘上去

        t[x].s=t[x].s*d%p;
        t[x].jia=t[x].jia*d%p;
        t[x].ch=t[x].ch*d%p;
    } else
    {
        down(x);//向下传递值 
        LO mid=(t[x].l+t[x].r)/2;
        if (l<=mid) cheng(l,r,x*2,d);//继续往下搜
        if (r>mid)cheng(l,r,x*2+1,d);
        t[x].s=(t[x*2+1].s+t[x*2].s)%p;//更新sum 
    }
    return;
}
void jf(LO l,LO r,LO x,LO d)
{
    if (l<=t[x].l&&t[x].r<=r)//全部包括 
    {
        t[x].jia=(t[x].jia+d)%p;
        t[x].s=(t[x].s+d*(t[x].r-t[x].l+1))%p;
    } else
    {
        down(x);//向下传递值 
        LO mid=(t[x].l+t[x].r)/2;
        if (l<=mid) jf(l,r,x*2,d);
        if (r>mid)jf(l,r,x*2+1,d);
        t[x].s=(t[x*2+1].s+t[x*2].s)%p;//更新sum 
    }
    return;
} 
long long qh(LO l,LO r,LO x)
{
    if (l<=t[x].l&&t[x].r<=r) //求得区间有这一部分，直接返回
         return t[x].s%p;
    else
    {
        down(x);//向下传递值 
        LO ans=0;
        LO mid=(t[x].l+t[x].r)/2;
        if (l<=mid) ans=qh(l,r,x*2)%p;
        if (r>mid)ans=ans+qh(l,r,x*2+1);
        return ans%p;
    }
}
int main() 
{
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&p);
    for (i=1;i<=n;i++)
    scanf("%lld",&a[i]);
    bt(1,n,1);//建树 
    for (i=1;i<=m;i++)
    {
        scanf("%lld",&c);//读入 
        if (c==1)//乘
        {
            scanf("%lld%lld%lld",&x,&y,&k);
            cheng(x,y,1,k);
        }
        if (c==3)//求和 
        {
            scanf("%lld%lld",&x,&y);
            sum=qh(x,y,1)%p;//求和 
            printf("%lld\n",sum);//结果 
        }
        if (c==2)//加 
        {
            scanf("%lld%lld%lld",&x,&y,&k);
            jf(x,y,1,k);
        }
    }
    return 0;
}