#1052. 【AHOI2009】维护序列
http://219.153.61.2:9000/problem/1052
https://www.luogu.com.cn/problem/P3373
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll read(){ ll x=0,f=1; char s=getchar(); while(!isdigit(s)) f*=(s=='-')? -1:1,s=getchar(); do x=(x<<1)+(x<<3)+(s^48),s=getchar(); while(isdigit(s)); return x*f; } const int N=100005; int n,mod,m; int a[N]; struct Sign{ int mul,add; }; struct Seg{ struct Node { int l,r,sum,isSigned; Sign sign; }node[N<<2]; void build(int l,int r,int x=1){ node[x].l=l,node[x].r=r; node[x].sign=(Sign){1,0}; if(l==r) { node[x].sum=a[l]; return; } int mid=(l+r)>>1; build(l,mid,x*2); build(mid+1,r,x*2+1); node[x].sum=(node[x*2].sum+node[x*2+1].sum)%mod; } void mix(int x,Sign sign){ node[x].sum=(1ll*node[x].sum*sign.mul +1ll*sign.add*(node[x].r-node[x].l+1))%mod; node[x].sign.mul=1ll*node[x].sign.mul*sign.mul%mod; node[x].sign.add=(1ll*node[x].sign.add*sign.mul+sign.add)%mod; node[x].isSigned=true; } void spread(int x){ if(node[x].isSigned){ mix(x*2,node[x].sign),mix(x*2+1, node[x].sign); node[x].sign=(Sign){1,0}; node[x].isSigned=false; } } int query(int l,int r,int x=1){ if(l<=node[x].l && node[x].r<=r) return node[x].sum; spread(x); int ans=0; if(node[x*2].r>=l) ans=query(l,r,x*2)+ans; if(node[x*2+1].l<=r) ans=query(l,r,x*2+1)+ans; return ans%mod; } void change(int l,int r,Sign sign,int x=1){ if(l<=node[x].l && node[x].r<=r){ mix(x,sign); return; } spread(x); if(node[x*2].r>=l) change(l,r,sign,x*2); if(node[x*2+1].l<=r) change(l,r,sign,x*2+1); node[x].sum=(node[x*2].sum+node[x*2+1].sum)%mod; } }T; int main(){ n=read(),m=read(),mod=read(); for(int i=1;i<=n;i++) a[i]=read(); T.build(1,n); for(int i=1;i<=m;i++){ int op=read(),l=read(),r=read(); if(op==1) T.change(l,r,(Sign){read(),0}); else if(op==2) T.change(l,r,(Sign){1,read()}); else if(op==3) printf("%d ",T.query(l,r)); } return 0; }