原题
题解：线段树区间乘法，lazy标记的更新对于我这种萌新来说是个难点qwq。先理清楚想好了再写。先乘后除，一步一步慢慢来。
//bzoj1798 [Ahoi2009]维护序列 #include<iostream> #include<cstdio> #include<cstring> #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 using namespace std; int n,p,m; long long sum[301000],col1[301000],col2[301000]; void pushup(int pos){sum[pos]=(sum[pos<<1]+sum[pos<<1|1])%p;} void pushdown(int pos,int len) { if(!col1[pos]&&col2[pos]==1) return; sum[pos<<1]=((sum[pos<<1]*col2[pos])+col1[pos]*(len-(len>>1)))%p; sum[pos<<1|1]=(sum[pos<<1|1]*col2[pos]+col1[pos]*(len>>1))%p; col2[pos<<1]=col2[pos<<1]*col2[pos]%p;col2[pos<<1|1]=col2[pos<<1|1]*col2[pos]%p; col1[pos<<1]=((col1[pos<<1]*col2[pos])%p+col1[pos])%p;col1[pos<<1|1]=((col1[pos<<1|1]*col2[pos])%p+col1[pos])%p; col1[pos]=0;col2[pos]=1; } void build(int l,int r,int pos) { col1[pos]=0;col2[pos]=1; if (l==r) {scanf("%lld",&sum[pos]);return;} int m=(l+r)>>1; build(lson);build(rson); pushup(pos); } void update_add(int L,int R,int add,int l,int r,int pos) { if(L<=l&&r<=R) { sum[pos]=sum[pos]+((r-l+1)*add)%p; col1[pos]=(col1[pos]+add)%p; return; } pushdown(pos,r-l+1); int m=(l+r)>>1; if (L<=m) update_add(L,R,add,lson); if (R>m) update_add(L,R,add,rson); pushup(pos); } void update_multi(int L,int R,int multi,int l,int r,int pos) { if(L<=l&&r<=R) { sum[pos]=sum[pos]*multi%p; col1[pos]=col1[pos]*multi%p;col2[pos]=col2[pos]*multi%p; return; } pushdown(pos,r-l+1); int m=(l+r)>>1; if (L<=m) update_multi(L,R,multi,lson); if (R>m) update_multi(L,R,multi,rson); pushup(pos); } long long query(int L,int R,int l,int r,int pos) { long long ret=0; if (L<=l&&r<=R) return sum[pos]; int m=(l+r)>>1; pushdown(pos,r-l+1); if (L<=m) ret=(ret+query(L,R,lson))%p; if (R>m) ret=(ret+query(L,R,rson))%p; return ret%p; } int main() { scanf("%d%d",&n,&p); build(1,n,1); scanf("%d",&m); while(m--) { int order,a,b,c; scanf("%d",&order); if (order==1) scanf("%d%d%d",&a,&b,&c),update_multi(a,b,c,1,n,1); else if (order==2) scanf("%d%d%d",&a,&b,&c),update_add(a,b,c,1,n,1); else {scanf("%d%d",&a,&b),printf("%lld\n",query(a,b,1,n,1)%p);/*for (int i=1;i<=20;i++) cout<<sum[i]<<' ';cout<<endl;*/} } return 0; }