这个板子不打就是手生……一段时间不会处理线段树了qwq，这个题难点就是在于下放标记
#include#include #include using namespace std;typedef long long lo;lo n,p,m,a[100010],x,y,z,fl,qwq;struct in{ lo l,r,s,f1,f2;}ter[400040];inline void re(lo &c){ c=0; char b=getchar(); while(b<'0'||b>'9') b=getchar(); while(b>='0'&&b<='9') c=c*10+b-'0',b=getchar();}inline void u(lo w){ ter[w].s=((ter[w<<1].s%p)+(ter[w<<1|1].s%p))%p;}inline void build(lo l,lo r,lo w){ ter[w]=(in){l,r,0,1,0}; if(l==r) { ter[w].s=a[l];return; } lo mid=l+r>>1; build(l,mid,w<<1),build(mid+1,r,w<<1|1); u(w);}inline void d(lo w){ lo f1=ter[w].f1,f2=ter[w].f2; if(f1==1&&f2==0) return; ter[w<<1].f1*=f1,ter[w<<1].f1%=p;//不管加法还是乘法的flag都要乘上他们父亲的乘法flag ter[w<<1|1].f1*=f1,ter[w<<1|1].f1%=p; ter[w<<1].f2*=f1,ter[w<<1].f2%=p; ter[w<<1|1].f2*=f1,ter[w<<1|1].f2%=p; ter[w<<1].f2+=f2,ter[w<<1].f2%=p;//加法还要加上 ter[w<<1|1].f2+=f2,ter[w<<1|1].f2%=p; ter[w<<1].s*=f1,ter[w<<1].s%=p;//先乘再加 ter[w<<1|1].s*=f1,ter[w<<1|1].s%=p; ter[w<<1].s+=f2*(ter[w<<1].r-ter[w<<1].l+1),ter[w<<1].s%=p; ter[w<<1|1].s+=f2*(ter[w<<1|1].r-ter[w<<1|1].l+1),ter[w<<1|1].s%=p; ter[w].f1=1,ter[w].f2=0;//乘法的flag赋为1是因为最起码*1，不能*0 }void cha1(lo l,lo r,lo jia,lo w){ if(ter[w].l==l&&ter[w].r==r)//乘法是一起乘 { ter[w].f1*=jia,ter[w].f1%=p; ter[w].f2*=jia,ter[w].f2%=p; ter[w].s*=jia,ter[w].s%=p; return; } d(w); lo mid=ter[w].l+ter[w].r>>1; if(r<=mid) cha1(l,r,jia,w<<1); else if(l>mid) cha1(l,r,jia,w<<1|1); else cha1(l,mid,jia,w<<1),cha1(mid+1,r,jia,w<<1|1); u(w);}void cha2(lo l,lo r,lo jia,lo w){ if(ter[w].l==l&&ter[w].r==r)//加法是单独加在加法的flag上 { ter[w].f2+=jia,ter[w].f2%=p; ter[w].s+=jia*(ter[w].r-ter[w].l+1),ter[w].s%=p; return; } d(w); lo mid=ter[w].l+ter[w].r>>1; if(r<=mid) cha2(l,r,jia,w<<1); else if(l>mid) cha2(l,r,jia,w<<1|1); else cha2(l,mid,jia,w<<1),cha2(mid+1,r,jia,w<<1|1); u(w);}lo ask(lo l,lo r,lo w){ if(ter[w].l==l&&ter[w].r==r) return ter[w].s; lo mid=ter[w].l+ter[w].r>>1,re=0; d(w); if(r<=mid) re+=ask(l,r,w<<1)%p; else if(l>mid) re+=ask(l,r,w<<1|1)%p; else re+=ask(l,mid,w<<1)%p,re+=ask(mid+1,r,w<<1|1)%p; u(w); return re;}int main(){ re(n),re(p); for(int i=1;i<=n;i++) re(a[i]); build(1,n,1);//建树 re(m); for(int i=1;i<=m;i++) { re(fl),re(x),re(y); if(fl==1) re(z),cha1(x,y,z,1);//区间乘 if(fl==2) re(z),cha2(x,y,z,1);//区间加 if(fl==3) qwq=ask(x,y,1)%p,printf("%lld\n",qwq);//查询 }}