#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int SIZE=100005;
struct Tree{
int l,r;
ll sum;
ll mul,add;
#define mul(x) t[x].mul
#define add(x) t[x].add
#define l(x) t[x].l
#define r(x) t[x].r
#define sum(x) t[x].sum
}t[4*SIZE];
ll a[SIZE];
int n,m;
ll k;
void update(int p){
sum(p)=(sum(p<<1)+sum(p<<1|1))%k;
}
void spread(int p){//先乘后加
sum(p<<1)=(sum(p<<1)*mul(p)+add(p)*(r(p<<1)-l(p<<1)))%k;
sum(p<<1|1)=(sum(p<<1|1)*mul(p)+add(p)*(r(p<<1|1)-l(p<<1|1)+1))%k;
mul(p<<1)=(mul(p<<1)*mul(p))%k;
mul(p<<1|1)=(mul(p<<1|1)*mul(p))%k;
add(p<<1)=(add(p<<1)*mul(p)+add(p))%k;
add(p<<1|1)=(add(p<<1|1)*mul(p)+add(p))%k;
add(p)=0;
mul(p)=1;
}
void Add(int p,int l,int r,ll x){
if(l<=l(p)&&r(p)<=r){
add(p)=(add(p)+x)%k;
sum(p)=(sum(p)+(r(p)-l(p)+1)*x)%k;
return;
}
int mid=(l(p)+r(p))>>1;
//cout<<p<<endl;
spread(p);
if(mid>=l) Add(p<<1,l,r,x);
if(r>mid) Add(p<<1|1,l,r,x);
update(p);
}
void Mul(int p,int l,int r,ll x){
if(l(p)<=l&&r(p)<=r){
add(p)=(add(p)*x)%k;
mul(p)=(mul(p)*x)%k;
sum(p)=(sum(p)*x)%k;
return;
}
spread(p);
int mid=(l(p)+r(p))>>1;
if(l<=mid) Mul(p<<1,l,r,x);
if(r>mid) Mul(p<<1|1,l,r,x);
update(p);
}
void build(int p,int l,int r){
l(p)=l,r(p)=r;
mul(p)=1;
if(l==r){
sum(p)=a[l]%k;
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
update(p);
}
ll ask(int p,int l,int r){
if(l<=l(p)&&r(p)<=r){
return sum(p);
}
spread(p);
int mid=(l(p)+r(p))>>1;
ll val=0;
if(mid>=l) val+=ask(p<<1,l,r);
if(mid<r) val+=ask(p<<1|1,l,r);
return val%k;
}
int main(){
scanf("%d%d%lld",&n,&m,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,1,n);
for(int i=1;i<=m;i++){
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
if(op==1){
ll x;
scanf("%lld",&x);
Mul(1,l,r,x);
}
else if(op==2){
ll x;
scanf("%lld",&x);
Add(1,l,r,x);
}
else{
printf("%lld\n",ask(1,l,r));
}
}
return 0;
}
样例:
5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4
标准输出:
17
2
我的输出:
17
30
可能是有关区间乘的出问题了?