一定要多取膜！不然一直卡60分！
在区间中进行更新并查询，很好想到用线段树
为了增加速度，我们可以用到lazy标记，不过这题有乘法，我们需要修改一下
定义结构体：
struct SegmentTree{ long long l,r; long long sum; long long addmark=0,mulmark=1;//加法的标记和乘法的标记}t[400010];//四倍开点 乘法更新：
if(x<=l&&y>=r) { t[id].sum=v%p*t[id].sum%p; t[id].mulmark=t[id].mulmark*v%p;//乘标要乘上去 t[id].addmark=t[id].addmark*v%p;//加标也要乘（想一想为什么？） return; } 加法更新
if(x<=l&&y>=r) { t[id].sum=(t[id].sum+v%p*(r-l+1)%p)%p;//这个不用解释吧 t[id].addmark=(t[id].addmark+v%p)%p; return; } 下传标记
void PushDown(long long id){ t[id*2].mulmark=t[id].mulmark%p*t[id*2].mulmark%p;//乘标是乘上去的 t[id*2+1].mulmark=t[id].mulmark%p*t[id*2+1].mulmark%p; t[id*2].addmark=(t[id*2].addmark%p*t[id].mulmark%p+t[id].addmark)%p;//加标要乘上下传下来的乘标 t[id*2+1].addmark=(t[id*2+1].addmark%p*t[id].mulmark%p+t[id].addmark)%p; t[id*2].sum=(t[id].mulmark%p*t[id*2].sum%p+t[id].addmark*(t[id*2].r-t[id*2].l+1)%p)%p;//先乘后加 t[id*2+1].sum=(t[id].mulmark%p*t[id*2+1].sum%p+t[id].addmark*(t[id*2+1].r-t[id*2+1].l+1)%p)%p; t[id].addmark=0;//记得清0 t[id].mulmark=1;} 贴完整代码
#include#define lson id*2,l,mid#define rson id*2+1,mid+1,rusing namespace std;long long n,m,p;struct SegmentTree{ long long l,r; long long sum; long long addmark=0,mulmark=1;}t[400010];void BuildTree(long long,long long,long long);void Update1(long long,long long,long long,long long,long long,long long);void Update2(long long,long long,long long,long long,long long,long long);long long Query(long long,long long,long long,long long,long long);void PushDown(long long);int main(){ scanf("%lld%lld",&n,&p); BuildTree(1,1,n); scanf("%lld",&m); for(long long i=1;i<=m;i++) { long long k; scanf("%lld",&k); if(k==1) { long long x,y,o; scanf("%lld%lld%lld",&x,&y,&o); Update1(1,1,n,x,y,o); } if(k==2) { long long x,y,o; scanf("%lld%lld%lld",&x,&y,&o); Update2(1,1,n,x,y,o); } if(k==3) { long long x,y; scanf("%lld%lld",&x,&y); printf("%lld\n",Query(1,1,n,x,y)%p); } }return 0;}void BuildTree(long long id,long long l,long long r){ t[id].l=l; t[id].r=r; if(l==r) { scanf("%lld",&t[id].sum); return; } long long mid=(l+r)>>1; BuildTree(lson); BuildTree(rson); t[id].sum=(t[id*2].sum+t[id*2+1].sum)%p;}void Update1(long long id,long long l,long long r,long long x,long long y,long long v){ long long mid=(l+r)>>1; if(x<=l&&y>=r) { t[id].sum=v%p*t[id].sum%p; t[id].mulmark=t[id].mulmark*v%p; t[id].addmark=t[id].addmark*v%p; return; } PushDown(id); if(x<=mid)Update1(id*2,l,mid,x,y,v); if(y>mid)Update1(id*2+1,mid+1,r,x,y,v); t[id].sum=(t[id*2].sum+t[id*2+1].sum)%p;}void Update2(long long id,long long l,long long r,long long x,long long y,long long v){ long long mid=(l+r)>>1; if(x<=l&&y>=r) { t[id].sum=(t[id].sum+v%p*(r-l+1)%p)%p; t[id].addmark=(t[id].addmark+v%p)%p; return; } PushDown(id); if(x<=mid)Update2(id*2,l,mid,x,y,v); if(y>mid)Update2(id*2+1,mid+1,r,x,y,v); t[id].sum=(t[id*2].sum+t[id*2+1].sum)%p;}long long Query(long long id,long long l,long long r,long long x,long long y){ long long mid=(l+r)>>1; long long sum=0; if(x<=l&&y>=r)return t[id].sum; PushDown(id); if(x<=mid)sum=(sum+Query(id*2,l,mid,x,y))%p; if(y>mid)sum=(sum+Query(id*2+1,mid+1,r,x,y))%p; return sum;}void PushDown(long long id){ t[id*2].mulmark=t[id].mulmark%p*t[id*2].mulmark%p; t[id*2+1].mulmark=t[id].mulmark%p*t[id*2+1].mulmark%p; t[id*2].addmark=(t[id*2].addmark%p*t[id].mulmark%p+t[id].addmark)%p; t[id*2+1].addmark=(t[id*2+1].addmark%p*t[id].mulmark%p+t[id].addmark)%p; t[id*2].sum=(t[id].mulmark%p*t[id*2].sum%p+t[id].addmark*(t[id*2].r-t[id*2].l+1)%p)%p; t[id*2+1].sum=(t[id].mulmark%p*t[id*2+1].sum%p+t[id].addmark*(t[id*2+1].r-t[id*2+1].l+1)%p)%p; t[id].addmark=0; t[id].mulmark=1;}