线段树2

``` #include<cstdio> #include<iostream> using namespace std; struct edge{ int l,r; long long w,add,mul; }s[800005]; int n,m,p; int num; int a; int build(int o,int left,int right) { s[o]=edge{left,right,0,0,1}; if(left==right) { scanf("%d",&num); return s[o].w=num; } int mid=(left+right)>>1; return s[o].w=(build(o<<1,left,mid)+build(o<<1|1,mid+1,right))%p; } void pushdown(int x) { s[x<<1].add=(s[x].add+s[x].mul*s[x<<1].add)%p; s[x<<1|1].add=(s[x].add+s[x].mul*s[x<<1|1].add)%p; s[x<<1].mul=(s[x].mul*s[x<<1].mul)%p; s[x<<1|1].mul=(s[x].mul*s[x<<1|1].mul)%p; s[x<<1].w=(s[x<<1].w*s[x].mul+s[x].add*(s[x<<1].r-s[x<<1].l+1))%p; s[x<<1|1].w=(s[x<<1|1].w*s[x].mul+s[x].add*(s[x<<1|1].r-s[x<<1|1].l+1))%p; s[x].mul=1; s[x].add=0; } long long search(int x,int left,int right) { pushdown(x); if(s[x].l>=left&&s[x].r<=right)return s[x].w%p; int mid=(s[x].l+s[x].r)>>1; return ((left<=mid?search(x<<1,left,right):0)+(right>mid?search(x<<1|1,left,right):0))%p; } void change(int x,int v,int a,int left,int right) { pushdown(x); if(a==1&&s[x].l>=left&&s[x].r<=right) { s[x].mul=(s[x].mul*v)%p; s[x].add=(s[x].add*v)%p; s[x].w=(s[x].w*s[x].mul)%p; return; } if(a==2&&s[x].l>=left&&s[x].r<=right) { s[x].add+=v; s[x].w=(s[x].w+s[x].add*(s[x].r-s[x].l+1))%p; return; } int mid=(s[x].l+s[x].r)>>1;; if(left<=mid)change(x<<1,v,a,left,right); if(right>mid)change(x<<1|1,v,a,left,right); s[x].w=s[x<<1].w+s[x<<1|1].w; } int main() { int x,y,k; scanf("%d%d%d",&n,&m,&p); build(1,1,n); for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&x,&y); if(a!=3) { scanf("%d",&k); change(1,k,a,x,y); } else printf("%lld\n",search(1,x,y)); } } ```