区间乘和区间加线段树
wenge
2020-08-15 08:56:24
```cpp
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define clr(a,b) memset(a,b,sizeof(a))
ll n,ans,q;
ll a[100005];
struct node{
ll s,add,mul;
}sgt[4*100005];
ll mod;
inline void pushup(ll i){
sgt[i].s=(sgt[i*2].s+sgt[i*2+1].s)%mod;
}
inline void pushdown(ll i,ll mid,ll l,ll r){
if(sgt[i].add||sgt[i].mul!=1){
sgt[i*2].s= (sgt[i*2].s*sgt[i].mul+(mid-l+1)*sgt[i].add)%mod;
sgt[i*2+1].s=(sgt[i*2+1].s*sgt[i].mul+(r-mid)*sgt[i].add)%mod;
sgt[i*2].mul= (sgt[i*2].mul*sgt[i].mul)%mod;
sgt[i*2+1].mul=(sgt[i*2+1].mul*sgt[i].mul)%mod;
sgt[i*2].add= (sgt[i*2].add*sgt[i].mul+sgt[i].add)%mod;
sgt[i*2+1].add=(sgt[i*2+1].add*sgt[i].mul+sgt[i].add)%mod;
sgt[i].mul=1;
sgt[i].add=0;
}
}
void build(ll l,ll r,ll i){
sgt[i].add=0,sgt[i].mul=1;
if(l==r){
sgt[i].s=a[l];
return;
}
ll mid=(l+r)>>1;
build(l,mid,i*2);
build(mid+1,r,i*2+1);
pushup(i);
}
ll query(ll s,ll t,ll l,ll r,ll i){
if(s<=l&&r<=t){
return sgt[i].s;
}
ll mid=(l+r)>>1;
pushdown(i,mid,l,r);
ll res=0;
if(mid>=s)res+=query(s,t,l,mid,i*2);
if(mid+1<=t)res+=query(s,t,mid+1,r,i*2+1);
pushup(i);
return res%mod;
}
void modify_add(ll s,ll t,ll l,ll r,ll i,ll x){
if(s<=l&&r<=t){
sgt[i].add=(sgt[i].add+x)%mod;
sgt[i].s=(sgt[i].s+(r-l+1)*x)%mod;
return;
}
ll mid=(l+r)>>1;
pushdown(i,mid,l,r);
if(mid>=s)modify_add(s,t,l,mid,i*2,x);
if(mid+1<=t)modify_add(s,t,mid+1,r,i*2+1,x);
pushup(i);
return;
}
void modify_mul(ll s,ll t,ll l,ll r,ll i,ll x){
if(s<=l&&r<=t){
sgt[i].mul=(sgt[i].mul*x)%mod;
sgt[i].add=(sgt[i].add*x)%mod;
sgt[i].s=(sgt[i].s*x)%mod;
return;
}
ll mid=(l+r)>>1;
pushdown(i,mid,l,r);
if(mid>=s)modify_mul(s,t,l,mid,i*2,x);
if(mid+1<=t)modify_mul(s,t,mid+1,r,i*2+1,x);
pushup(i);
return;
}
int main(){
//freopen("P1429_6.in","r",stdin);
//freopen("match.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q>>mod;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,n,1);
for(int i=1;i<=q;i++){
ll type,l,r,x;
cin>>type>>l>>r;
if(type==1){
cin>>x;
modify_mul(l,r,1,n,1,x);
}
else if(type==2){
cin>>x;
modify_add(l,r,1,n,1,x);
}
else{
cout<<query(l,r,1,n,1)<<"\n";
}
}
return 0;
}
```