C25 线段树 区间乘加 P3373 线段树2

#include<bits/stdc++.h>
using namespace std;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
typedef long long LL;
const int N=1e5+5;
struct trnode{int l,r;LL s,a,t;}tr[4*N];LL P,a[N];
void pushup(int p){tr[p].s=(tr[lc(p)].s+tr[rc(p)].s)%P;}
void pushdown(int p)
{
	LL t=tr[p].t,a=tr[p].a;
    if(t!=1)
	{
        tr[lc(p)].s=tr[lc(p)].s*t%P;
        tr[rc(p)].s=tr[rc(p)].s*t%P;
        tr[lc(p)].a=tr[lc(p)].a*t%P;
        tr[rc(p)].a=tr[rc(p)].a*t%P;
        tr[lc(p)].t=tr[lc(p)].t*t%P;
        tr[rc(p)].t=tr[rc(p)].t*t%P;
        tr[p].t=1;
    }
    if(a!=0)
	{
        tr[lc(p)].s=(tr[lc(p)].s+a*(tr[lc(p)].r-tr[lc(p)].l+1))%P;
        tr[rc(p)].s=(tr[rc(p)].s+a*(tr[rc(p)].r-tr[rc(p)].l+1))%P;
        tr[lc(p)].a=(tr[lc(p)].a+a)%P;
        tr[rc(p)].a=(tr[rc(p)].a+a)%P;
        tr[p].a=0;
    }
}
void bt(int p,int l,int r)
{
    tr[p]=trnode{l,r,0,0,1};
	if(l==r){tr[p].s=a[l];return ;}
	int m=(l+r)>>1;
    bt(lc(p),l,m),bt(rc(p),m+1,r);
    pushup(p);
}
void change(int p,int l,int r,LL t,int op)
{
	if(r<tr[p].l || tr[p].r<l) return ;
    if(l<=tr[p].l&&tr[p].r<=r)
	{
        if(op==1)
		{
			tr[p].s=tr[p].s*t%P;
			tr[p].a=tr[p].a*t%P;
			tr[p].t=tr[p].t*t%P;
		}
		else
		{
			tr[p].s=(tr[p].s+t*(tr[p].r-tr[p].l+1)%P)%P;
			tr[p].a=(tr[p].a+t)%P;
		}
		
        return;
    }
    pushdown(p);
    change(lc(p),l,r,t,op);change(rc(p),l,r,t,op);
    pushup(p);
}
LL ans;
void query(int p,int l,int r)
{
	if(r<tr[p].l || tr[p].r<l) return ;
    if(l<=tr[p].l&&tr[p].r<=r){ans=(ans+tr[p].s)%P;return ;}
    pushdown(p);
    query(lc(p),l,r);query(rc(p),l,r);
}
int main()
{
    int n;scanf("%d%lld",&n,&P);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    bt(1,1,n);
    int m;scanf("%d",&m);
    for(int i=1;i<=m;i++)
	{
        int op,x,y;LL c;scanf("%d",&op);
        if(op==1)
		{
            scanf("%d%d%lld",&x,&y,&c);
            change(1,x,y,c,op);
        }
        else if(op==2)
		{
            scanf("%d%d%lld",&x,&y,&c);
            change(1,x,y,c,op);
        }
        else
		{
            scanf("%d%d",&x,&y);
            ans=0;query(1,x,y);printf("%lld\n",ans);
        }
    }
    return 0;
}