题目：P3373

代码：

#include <bits/stdc++.h>
using namespace std;
//#define int long long
//#define ln (d<<1)
//#define rn (d<<1|1)
//#define mid ((r+l)>>1)
//#define LL long long
long long x,y,z;
long long m[1000005];
struct node{
	long long l,r,sum;
	long long add;
	long long mul;
};
node tr[4000005];
void js(long long q,long long l,long long r){
	tr[q]={l,r,m[l]};
	if(l==r){
		return ;
	}
	long long mid=(l+r)/2;
	js(q*2,l,mid);
	js(q*2+1,mid+1,r);
	tr[q].sum=tr[q*2].sum+tr[q*2+1].sum;
}
/*
void intn(int d,int l,int r) {
	tree[d].l=l;
	tree[d].r=r;
	if(l==r) {
		tree[d].num=(LL)(a[l]);
		return;
	}
	intn(ln,l,mid);
	intn(rn,mid+1,r);
	tree[d].num=tree[ln].num+tree[rn].num;
	tree[d].num%=mod;
}
*/
void ddjf(long long q,long long n,long long k){
	if(tr[q].l==n&&tr[q].r==n) {
		tr[q].sum+=k;
		return ;
	}
	long long mid=(tr[q].l+tr[q].r)/2;
	if(n<=mid) ddjf(q*2,n,k);
	if(n>mid) ddjf(q*2+1,n,k);
	tr[q].sum=tr[q*2].sum+tr[q*2+1].sum;
}
void calc(node &f,int a,int b){
	f.sum=(f.sum*a+(f.r-f.l+1)*a)%z;
	f.mul=f.mul*a%z;
	f.add=(f.add*a+b)%z;
}
void qjgg(long long q,long long ml,long long mr,long long t,long long k){
	if(mr<tr[q].l||ml>tr[q].r) return ;
	if(ml<=tr[q].l&&tr[q].r<=mr){
		calc(tr[q],t,k);
		return ;
	}
	//long long u=tr[q].l+tr[q].r>>1;
	calc(tr[q*2],tr[q].mul,tr[q].add);
	calc(tr[q*2+1],tr[q].mul,tr[q].add);
	tr[q].mul=1;
	tr[q].add=0;
	qjgg(q*2,ml,mr,t,k);
	qjgg(q*2+1,ml,mr,t,k);
	tr[q].sum=(tr[q*2].sum+tr[q*2+1].sum)%z;
}
long long qjqh(long long q,long long ml,long long mr){
	//cout<<q<<" "<<tr[q].l<<" "<<tr[q].r<<" "<<tr[q].sum<<"\n";
	if(tr[q].l>=ml&&tr[q].r<=mr) return tr[q].sum;
	long long mid=(tr[q].l+tr[q].r)/2;
	calc(tr[q*2],tr[q].mul,tr[q].add);
	calc(tr[q*2+1],tr[q].mul,tr[q].add);
	tr[q].mul=1;
	tr[q].add=0;
	long long summ=0;
	if(/*tr[q].l<=ml*/ml<=mid/*&&tr[q].r>=mr*/){
		summ+= qjqh(q*2,ml,mr);
	}
	if(/*tr[q].l>=ml&&*/mr>mid/*tr[q].r>=mr*/){
		summ+= qjqh(q*2+1,ml,mr);
	}
	return summ;
}
signed main(){
	cin>>x>>y>>z;
	for(int i=1;i<=x;i++){
		cin>>m[i];
	}
	js(1,1,x);
	//for(int j=1;j<=x*4;j++){
	//            cout<<"        "<<tr[j].l<<" "<<tr[j].r<<" "<<tr[j].sum<<endl;
    //        }
	//for(int i=1;i<=x*4;i++){
	//	cout<<"     "<<tr[i].l<<" "<<tr[i].r<<" "<<tr[i].sum<<endl;
	//}
	for(long long i=1;i<=y;i++){
		long long a,b,c,d;
		cin>>a;
		if(a==3){
			cin>>b>>c;
			cout<<qjqh(1,b,c)<<endl;
				//for(int j=1;j<=x*4;j++){
	            //	cout<<"        "<<tr[j].l<<" "<<tr[j].r<<" "<<tr[j].sum<<endl;
	            //}
		}
		else{
		cin>>b>>c>>d;
			if(a==1){
				qjgg(1,b,c,d,0);
			}
			else{
				qjgg(1,b,c,1,d);
			}
		//	for(int j=1;j<=x*4;j++){
	    //        cout<<"        "<<tr[j].l<<" "<<tr[j].r<<" "<<tr[j].sum<<endl;
        //   }
		}
	}
	return 0;
}