如题，已知一个数列，你需要进行下面三种操作：
1.将某区间每一个数乘上x
2.将某区间每一个数加上x
3.求出某区间每一个数的和
输入格式：
第一行包含三个整数N、M、P，分别表示该数列数字的个数、操作的总个数和模数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数乘上k
操作2： 格式：2 x y k 含义：将区间[x,y]内每个数加上k
操作3： 格式：3 x y 含义：输出区间[x,y]内每个数的和对P取模所得的结果
输出格式：
输出包含若干行整数，即为所有操作3的结果。
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^）
样例说明：
故输出应为17、2（40 mod 38=2）
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ll long long
#define N 10000005
using namespace std;
ll a[N],tr[N*4],mo,mul[N*4],add[N*4],n,m;
void build(ll p,ll l,ll r){
mul[p]=1;
if (l==r){
tr[p]=a[l];
return ;
}
ll mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tr[p]=(tr[p*2]+tr[p*2+1])%mo;
return ;
}
void ADD(ll p,ll l,ll r,ll mulk,ll sumk){
tr[p]=(tr[p]*mulk+(r-l+1)*sumk)%mo;
add[p]=(add[p]*mulk+sumk)%mo;
mul[p]=(mul[p]*mulk)%mo;
return ;
}
void pushdown(ll p,ll l,ll r){
ll mid=(l+r)/2;
ADD(p*2,l,mid,mul[p],add[p]);
ADD(p*2+1,mid+1,r,mul[p],add[p]);
add[p]=0;
mul[p]=1;
return ;
}
void changemul(ll p,ll l,ll r,ll x,ll y,ll v){
if (x<=l&&r<=y){
ADD(p,l,r,v,0);
return ;
}
pushdown(p,l,r);
ll mid=(l+r)/2;
if (x<=mid) changemul(p*2,l,mid,x,y,v);
if (mid<y) changemul(p*2+1,mid+1,r,x,y,v);
tr[p]=(tr[p*2]+tr[p*2+1])%mo;
}
void changesum(ll p,ll l,ll r,ll x,ll y,ll v){
if (x<=l&&r<=y){
ADD(p,l,r,1,v);
return ;
}
pushdown(p,l,r);
ll mid=(l+r)/2;
if (x<=mid) changesum(p*2,l,mid,x,y,v);
if (mid<y) changesum(p*2+1,mid+1,r,x,y,v);
tr[p]=(tr[p*2]+tr[p*2+1])%mo;
}
ll query(ll p,ll l,ll r,ll x,ll y){
if (x<=l&&r<=y) return tr[p] ;
pushdown(p,l,r);
ll mid=(l+r)/2,res=0;
if (x<=mid) res+=query(p*2,l,mid,x,y);
if (mid<y) res+=query(p*2+1,mid+1,r,x,y);
return res%mo;
}
int main(){
scanf("%lld %lld %lld",&n,&m,&mo);
for (ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
build(1,1,n);
for (ll i=1;i<=m;i++){
ll n1=0;ll x,y,k;
scanf("%lld",&n1);
if (n1==1){
scanf("%lld %lld %lld",&x,&y,&k);
changemul(1,1,n,x,y,k);
}
if (n1==2){
scanf("%lld %lld %lld",&x,&y,&k);
changesum(1,1,n,x,y,k);
}
if (n1==3){
scanf("%lld %lld",&x,&y);
printf("%lld\n",query(1,1,n,x,y));
}
}
return 0;
}
原文：https://www.cnblogs.com/xiongchongwen/p/11206530.html