提交记录

代码：

#include<iostream>
#define ll long long
using namespace std;
struct node{
	int l,r;
	ll value;
	int add=0;
	int mul=1;
	int mid(){ return (l+r)>>1;	}
	int len(){ return r-l+1; }
}tree[400010];
int a[100010];
int n,m,p;
inline void push_up(int k){
	tree[k].value=(tree[k<<1].value+tree[k<<1|1].value)%p;
}inline void push_down(int k){
	if(tree[k].mul==1&&tree[k].add==0)
        return ;
    tree[k<<1].value=((tree[k<<1].value*tree[k].mul)%p+(tree[k<<1].len()*tree[k].add)%p)%p;	
    tree[k<<1|1].value=((tree[k<<1|1].value*tree[k].mul)%p+(tree[k<<1|1].len()*tree[k].add)%p)%p;
	tree[k<<1].mul=(tree[k<<1].mul*tree[k].mul)%p;
	tree[k<<1|1].mul=(tree[k<<1|1].mul*tree[k].mul)%p;	
	tree[k<<1].add=((tree[k<<1].add*tree[k].mul)%p+tree[k].add)%p;
	tree[k<<1|1].add=((tree[k<<1|1].add*tree[k].mul)%p+tree[k].add)%p;
	tree[k].mul=1;
	tree[k].add=0;
	return ;
}void build(int k,int l,int r){
	tree[k].l=l,tree[k].r=r;
	if(l==r){
		tree[k].value=a[l]%p;
		return ;
	}int mid=tree[k].mid();
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	push_up(k);
}void update1(int k,int l,int r,int x){
	if(l<=tree[k].l&&tree[k].r<=r){
		tree[k].value=(tree[k].value*x)%p;
		tree[k].mul=(tree[k].mul*x)%p;
		tree[k].add=(tree[k].add*x)%p;
		return ;
	}push_down(k);
	int mid=tree[k].mid();
	if(l<=mid) update1(k<<1,l,r,x);
	if(r>mid) update1(k<<1|1,l,r,x);
	push_up(k);
}void update2(int k,int l,int r,int x){
	if(l<=tree[k].l&&tree[k].r<=r){
		tree[k].add=(tree[k].add+x)%p;
		tree[k].value=(tree[k].value+(tree[k].len()*x)%p)%p;
		return ;
	}push_down(k);
	int mid=tree[k].mid();
	if(l<=mid) update2(k<<1,l,r,x);
	if(r>mid) update2(k<<1|1,l,r,x);
	push_up(k);
}ll query(int k,int l,int r){
	if(l<=tree[k].l&&tree[k].r<=r)
		return tree[k].value;
	push_down(k);
	int mid=tree[k].mid();
	ll res=0;
	if(l<=mid) res=(res+query(k<<1,l,r))%p;
	if(r>mid) res=(res+query(k<<1|1,l,r))%p;
	return res;
}int main(){
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	build(1,1,n);
	int op,x,y,z;
	++m;
	while(--m){
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d%d",&x,&y,&z);
			update1(1,x,y,z);
		}else if(op==2){
			scanf("%d%d%d",&x,&y,&z);
			update2(1,x,y,z);
		}else{
			scanf("%d%d",&x,&y);
			printf("%lld\n",query(1,x,y));
		}
	}return 0;
}