题目链接:https://www.luogu.org/problemnew/show/P2023
把P3373改一改直接粘过来就A
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lson left, mid, rt<<1
#define rson mid+1, right, rt<<1|1
#define ll long long
using namespace std;
const int maxn = ;
ll n, m, addlazy[maxn<<], mullazy[maxn<<], ans[maxn<<], mod, x,y,k;
void PushUP(ll rt)
{
ans[rt] = (ans[rt<<] + ans[rt<<|])%mod;
}
void build(ll left, ll right, ll rt)
{
addlazy[rt] = ;
mullazy[rt] = ;
if(right == left)
{
scanf("%d",&ans[rt]);
return ;
}
ll mid = (left+right) >> ;
build(lson);
build(rson);
PushUP(rt);
}
void PushDOWN(ll rt, ll mid, ll left, ll right)
{
mullazy[rt<<]=(mullazy[rt<<]*mullazy[rt])%mod;
mullazy[rt<<|]=(mullazy[rt<<|]*mullazy[rt])%mod;
addlazy[rt<<]=(addlazy[rt<<]*mullazy[rt])%mod;
addlazy[rt<<|]=(addlazy[rt<<|]*mullazy[rt])%mod;
ans[rt<<]=(ans[rt<<]*mullazy[rt])%mod;
ans[rt<<|]=(ans[rt<<|]*mullazy[rt])%mod;
mullazy[rt]=;
addlazy[rt<<]=(addlazy[rt<<]+addlazy[rt])%mod;
addlazy[rt<<|]=(addlazy[rt<<|]+addlazy[rt])%mod;
ans[rt<<]=(ans[rt<<]+(mid-left+)*addlazy[rt])%mod;
ans[rt<<|]=(ans[rt<<|]+(right-mid)*addlazy[rt])%mod;
addlazy[rt]=;
}
void mulupdate(ll l, ll r, ll add, ll left, ll right, ll rt)
{
if(l<=left&&r>=right)
{
addlazy[rt] = (addlazy[rt]*add)%mod;
mullazy[rt] = (mullazy[rt]*add)%mod;
ans[rt] = (add*ans[rt])%mod;
return;
}
ll mid = (left+right)>>;
if(mullazy[rt]!=||addlazy[rt]>=) PushDOWN(rt,mid,left,right);
if(l<=mid) mulupdate(l,r,add,lson);
if(r>mid) mulupdate(l,r,add,rson);
PushUP(rt);
}
void addupdate(ll l, ll r, ll add, ll left, ll right, ll rt)
{
if(l<=left&&r>=right)
{
addlazy[rt]= (addlazy[rt]+add)%mod;
ans[rt] = (ans[rt] + add*(right-left+))%mod;
return;
}
ll mid = (left+right)>>;
if(mullazy[rt]!=||addlazy[rt]>=) PushDOWN(rt,mid,left,right);
if(l<=mid) addupdate(l,r,add,lson);
if(r>mid) addupdate(l,r,add,rson);
PushUP(rt);
}
ll query(ll l, ll r, ll left, ll right, ll rt)
{
ll res = ;
if(l <= left&&r >= right) return ans[rt]%mod;
ll mid = (left+right) >> ;
if(mullazy[rt]!=||addlazy[rt]>=) PushDOWN(rt, mid, left, right);
if(l <= mid) res = (res+query(l,r,lson))%mod;
if(r > mid) res = (res+query(l,r,rson))%mod;
return res%mod;
}
int main()
{
scanf("%d%d",&n,&mod);
build(,n,);
scanf("%d",&m);
while(m--)
{
int p;
scanf("%d",&p);
if(p == )
{
scanf("%d%d%d",&x,&y,&k);
mulupdate(x,y,k,,n,);
}
if(p == )
{
scanf("%d%d%d",&x,&y,&k);
addupdate(x,y,k,,n,);
}
if(p == )
{
scanf("%d%d",&x,&y);
printf("%d\n",query(x,y,,n,));
}
}
return ;
}