rt,本人的代码手打的,样例过不了,看看题解也没查出不同,救救孩子QWQ
#include<bits/stdc++.h>
#define reg register ll
#define ll long long
using namespace std;
struct node{
ll l,r,data,mul,add;
}tr[400005];
ll n,m,p,a[100005];
void build(ll l,ll r,ll id){
tr[id].l=l;
tr[id].r=r;
tr[id].mul=1;
if(l==r){
tr[id].data=a[l]%p;
return;
}
ll mid=(l+r)>>1;
build(l,mid,id<<1);
build(mid+1,r,id<<1|1);
tr[id].data=(tr[id<<1].data+tr[id<<1|1].data)%p;
}
void push_down(ll id){
ll mid=(tr[id].l+tr[id].r)>>1;
tr[id<<1].data=(tr[id<<1].data*tr[id].mul+tr[id].add*(mid-tr[id].l+1))%p;
tr[id<<1|1].data=(tr[id<<1|1].data*tr[id].mul+tr[id].add*(tr[id].r-mid))%p;
tr[id<<1].mul=(tr[id<<1].mul*tr[id].mul)%p;
tr[id<<1|1].mul=(tr[id<<1|1].mul*tr[id].mul)%p;
tr[id<<1].add=(tr[id<<1].add*tr[id].mul+tr[id].add)%p;
tr[id<<1|1].add=(tr[id<<1|1].add*tr[id].mul+tr[id].add)%p;
tr[id].add=0;tr[id].mul=1;
}
void upd_add(ll id,ll l,ll r,ll k){
if(tr[id].r<l||tr[id].l>r){return;}
if(tr[id].r<=r&&tr[id].l>=l){
tr[id].data=(tr[id].data+k*(tr[id].r-tr[id].l))%p;
tr[id].add=(tr[id].add+k)%p;
return;
}
push_down(id);
upd_add(id<<1,l,r,k);
upd_add(id<<1|1,l,r,k);
tr[id].data=(tr[id<<1].data+tr[id<<1|1].data)%p;
}
void upd_mul(ll id,ll l,ll r,ll k){
if(tr[id].r<l||tr[id].l>r){return;}
if(tr[id].r<=r&&tr[id].l>=l){
tr[id].data=(tr[id].data*k)%p;
tr[id].mul=(tr[id].mul*k)%p;
tr[id].add=(tr[id].add*k)%p;
return;
}
push_down(id);
upd_mul(id<<1,l,r,k);
upd_mul(id<<1|1,l,r,k);
tr[id].data=(tr[id<<1].data+tr[id<<1|1].data)%p;
}
ll query(ll id,ll l,ll r){
if(tr[id].r<l||tr[id].l>r){return 0;}
if(tr[id].r<=r&&tr[id].l>=l){
return tr[id].data;
}
push_down(id);
ll tot=0;
tot=(tot+query(id<<1,l,r))%p;
tot=(tot+query(id<<1|1,l,r))%p;
return tot;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>p;
for(reg i=1;i<=n;i++){
cin>>a[i];
}
build(1,n,1);
for(reg i=1;i<=m;i++){
int type,l,r;
cin>>type>>l>>r;
if(type==1){
int k;
cin>>k;
upd_mul(1,l,r,k);
}else if(type==2){
int k;
cin>>k;
upd_add(1,l,r,k);
}else{
cout<<query(1,l,r)%p<<endl;
}
}
return 0;
}