题目描述

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式： (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。

思路

加两个标记一个乘一个加，跑lazy+线段树模板就可以了
写的时候忘了将值向上传递
最后没有输出lld型。。。

#include <stdio.h>
#define maxn 1000001
#define LL long long
int n,mod;
struct tree
{
    LL x,addlazy,mullazy;
}t[maxn];
LL a[maxn];
int k=0;
inline int read()
{
    int x=0,p=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')p=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*p;
}
int pushdown(int p,int l,int r)
{
    int m=(l+r)>>1;
    if (l<r)
    {
        t[p<<1].mullazy=(t[p<<1].mullazy*t[p].mullazy)%mod;
        t[p<<1|1].mullazy=(t[p<<1|1].mullazy*t[p].mullazy)%mod;
        t[p<<1].addlazy=(t[p<<1].addlazy*t[p].mullazy+t[p].addlazy)%mod;
        t[p<<1|1].addlazy=(t[p<<1|1].addlazy*t[p].mullazy+t[p].addlazy)%mod;
        t[p<<1].x=(t[p<<1].x*t[p].mullazy+t[p].addlazy*(m-l+1))%mod;
        t[p<<1|1].x=(t[p<<1|1].x*t[p].mullazy+t[p].addlazy*(r-m))%mod;
    } 
    t[p].mullazy=1;
    t[p].addlazy=0;
}
int add(int p,int l,int r,int x,int y,int k)
{
    if (t[p].addlazy!=0||t[p].mullazy!=1) 
        pushdown(p,l,r);
    if (l==x&&r==y)
    {
        t[p].addlazy=k;
        t[p].x=(t[p].x+k*(r-l+1))%mod;
        return 0;
    }
    int m=(l+r)>>1;
    if (m>=y) add(p<<1,l,m,x,y,k);
    else if (m<x) add(p<<1|1,m+1,r,x,y,k);
    else 
    {
        add(p<<1,l,m,x,m,k);
        add(p<<1|1,m+1,r,m+1,y,k);
    }
    t[p].x=(t[p<<1].x+t[p<<1|1].x)%mod;
}
int mul(int p,int l,int r,int x,int y,int k)
{
    if (t[p].addlazy!=0||t[p].mullazy!=1) 
        pushdown(p,l,r);
    if (l==x&&r==y)
    {
        t[p].mullazy=k;
        t[p].x=(t[p].x*k)%mod;
        return 0;
    }
    int m=(l+r)>>1;
    if (m>=y) mul(p<<1,l,m,x,y,k);
    else if (m<x) mul(p<<1|1,m+1,r,x,y,k);
    else 
    {
        mul(p<<1,l,m,x,m,k);
        mul(p<<1|1,m+1,r,m+1,y,k);
    }
    t[p].x=(t[p<<1].x+t[p<<1|1].x)%mod;
}
LL find(int p,int l,int r,int x,int y)
{
    LL xx=0;
    if (t[p].addlazy!=0||t[p].mullazy!=1)
        pushdown(p,l,r);
    if (l==x&&r==y)
        return (t[p].x*t[p].mullazy+t[p].addlazy*(r-l+1))%mod;
    int m=(l+r)>>1;
    if (m>=y) xx=find(p<<1,l,m,x,y);
    else if (m<x) xx=find(p<<1|1,m+1,r,x,y);
    else
    {
        xx=(find(p<<1,l,m,x,m)+find(p<<1|1,m+1,r,m+1,y))%mod;
    }
    return xx;
}
int build(int p,int l,int r)
{
    t[p].mullazy=1;
    int m=(l+r)>>1;
    if (l==r)
    {
        t[p].x=a[l];
        return 0;
    }
    build(p<<1,l,m);
    build(p<<1|1,m+1,r);
    t[p].x=(t[p<<1].x+t[p<<1|1].x)%mod;
}
int main()
{
    n=read(); mod=read();
    for (int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,1,n);

    int m=read();
    for (int i=1;i<=m;i++)
    {
        int h=read();
        if (h==1)
        {
            int x=read(),y=read(),k=read();
            mul(1,1,n,x,y,k);
        }
        if (h==2)
        {
            int x=read(),y=read(),k=read();
            add(1,1,n,x,y,k);
        }
        if (h==3)
        {
            int x=read(),y=read();
            printf("%lld\n",find(1,1,n,x,y));
        }
    }
}