#include<stdio.h> #include<math.h> #include<string.h> #include<algorithm> int a[100005],p; static const int MAXN=400000; struct Segment_tree///1.把一段区间变成同一个数，2求任意区间的和 { int size;///区间容量 struct Node { long long a; long long b; long long sum; int len; void fun(long long a1,long long b1)///复合一个新标记 { a=a*a1%p; b=(b*a1+b1)%p; } void use() { sum=(sum*a+b*len)%p; } void clear() { a=1; b=0; } bool islazy() { return a!=1||b!=0; } } node[MAXN]; void update(int pos)///结点更新函数 { if(pos>=size)///判断是叶子 { node[pos].sum=a[pos-size]%p; } else { node[pos].sum=(node[pos<<1].sum+node[pos<<1^1].sum)%p; node[pos].len=node[pos<<1].len+node[pos<<1^1].len; } if(node[pos].islazy())///注意如果有懒惰标记的话要把懒惰标记用掉 node[pos].use(); } void build(int n)///申请空空间 { n+=4;///保险起见，申请时，申请得稍微大一点 size=1; while(size<n)///计算几个刚好能套住整个区间的区间容量 size<<=1; memset(node,0,sizeof(node)); } void build(int n,int arr[])///申请空间，并建树 { build(n); int i; for(i=1; i<=n; i++) { node[i+size].sum=arr[i];///把数组铺在底层 node[i+size].clear(); } for(i=size; i<size+size; i++) { node[i].len=1; node[i].clear(); } for(i=size-1; i>0; i--) { node[i].clear(); update(i);///数值更新上去 } } void putdown(int s,int t)///将标记放下 { if(s>1)///判断是否到顶，没达到顶继续往上爬 { putdown(s>>1,t>>1); } if(node[s].islazy())///判断有没有标记，如果有标记话，下放给孩子 { node[s<<1].fun(node[s].a,node[s].b); node[s<<1^1].fun(node[s].a,node[s].b); node[s].clear(); } if(node[t].islazy()) { node[t<<1].fun(node[t].a,node[t].b); node[t<<1^1].fun(node[t].a,node[t].b); node[t].clear(); } } void add(int l,int r,int x) { int s=l+size-1; int t=r+size+1; putdown(s>>1,t>>1); ///更新标记>更新值>查询查询值 for(; s^t^1; s>>=1,t>>=1) { // printf("[%d %d] ",s,t); if(~s&1) node[s^1].fun(1,x); if(t&1) node[t^1].fun(1,x); update(s); update(t); update(s^1); update(t^1); } while(s)///一直更新到顶 { update(s); update(s^1); s>>=1; } } void mul(int l,int r,int x) { int s=l+size-1; int t=r+size+1; putdown(s>>1,t>>1); ///更新标记>更新值>查询查询值 for(; s^t^1; s>>=1,t>>=1) { // printf("[%d %d] ",s,t); if(~s&1) node[s^1].fun(x,0); if(t&1) node[t^1].fun(x,0); update(s); update(t); update(s^1); update(t^1); } while(s)///一直更新到顶 { update(s); update(s^1); s>>=1; } } int query(int l,int r) { int s=l+size-1; int t=r+size+1; putdown(s>>1,t>>1); long long sum=0; ///更新标记>更新值>查询查询值 for(; s^t^1; s>>=1,t>>=1) { update(s); update(t); update(s^1); update(t^1); // printf("[%d %d] ",s,t); if(~s&1) { sum+=node[s^1].sum; } if(t&1) { sum+=node[t^1].sum; } } while(s)///一直更新到顶 { update(s); update(s^1); s>>=1; } return sum%p; } void put() { int i=1,j=1,s=size*4,k,len=3; for(i=1; i<=2*size-1; i++) { if(i==j) { puts(""); j<<=1; s>>=1; for(k=0; k<len*(s/2-1); k++) printf(" "); } printf("%3d",node[i].islazy()); for(k=0; k<len*(s-1); k++) printf(" "); } puts(""); } } tree; int main() { int n,i,t,x,y,cas=1,l,r,m,op; scanf("%d%d",&n,&p); for(i=1; i<=n; i++) scanf("%d",&a[i]); tree.build(n,a); // tree.put(); scanf("%d",&m); while(m--) { scanf("%d",&op); if(op==1) { scanf("%d%d%d",&l,&r,&x); tree.mul(l,r,x); } else if(op==2) { scanf("%d%d%d",&l,&r,&x); tree.add(l,r,x); } else { scanf("%d%d",&l,&r); printf("%d ",tree.query(l,r)); } } return 0; }