P3373 【模板】线段树 2
乘法优先还是加法优先
①加法优先，即规定好segtree[root*2].value=((segtree[root*2].value segtree[root].add)*segtree[root].mul)%p，问题是这样的话非常不容易进行更新操作，假如改变一下add的数值，mul也要联动变成奇奇怪怪的分数小数损失精度，我们内心是很拒绝的；
②乘法优先，即规定好segtree[root*2].value=(segtree[root*2].value*segtree[root].mul segtree[root].add*(本区间长度))%p，这样的话假如改变add的数值就只改变add，改变mul的时候把add也对应的乘一下就可以了，没有精度损失，看起来很不错。
（来自洛谷第一篇分析）
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define ll long long
const int maxn = 100005;
ll mod;
ll a[maxn];
struct Node{
int l,r;
ll pre,add,mul;
}t[4*maxn 5];
void build(int p,int l,int r){
t[p].l = l; t[p].r = r;
if(l==r){
t[p].pre = a[l]; t[p].mul = 1;
return ;
}
t[p].mul = 1;
int mid = l r>>1;
build(p*2,l,mid);
build(p*2 1,mid 1,r);
t[p].pre = (t[2*p].pre t[2*p 1].pre)%mod;
}
void spread(int p){
t[2*p].pre = (t[2*p].pre*t[p].mul t[p].add*(t[2*p].r-t[2*p].l 1))%mod;
t[2*p 1].pre = (t[2*p 1].pre*t[p].mul t[p].add*(t[2*p 1].r-t[2*p 1].l 1))%mod;
t[2*p].mul = (t[p].mul*t[2*p].mul)%mod;
t[2*p 1].mul = (t[p].mul*t[2*p 1].mul)%mod;
t[2*p].add = (t[2*p].add*t[p].mul t[p].add)%mod;
t[2*p 1].add = (t[2*p 1].add*t[p].mul t[p].add)%mod;
t[p].mul = 1;
t[p].add = 0;
}
void change1(int p,int l,int r,ll z){//加法更新
if(l<=t[p].l&&r>=t[p].r){
t[p].pre =z*(t[p].r-t[p].l 1);t[p].pre%=mod;
t[p].add =z;t[p].add%=mod;//加法只处理加法
return ;
}
spread(p);
int mid = t[p].l t[p].r>>1;
if(l<=mid)change1(p*2,l,r,z);
if(r>mid)change1(p*2 1,l,r,z);
t[p].pre = (t[2*p].pre t[2*p 1].pre)%mod;
}
void change2(int p,int l,int r,ll z){//乘法更新
if(l<=t[p].l&&r>=t[p].r){
t[p].pre=(t[p].pre*z)%mod;
t[p].mul=(t[p].mul*z)%mod;
t[p].add=(t[p].add*z)%mod;//乘法 则加全都乘
return ;
}
spread(p);
int mid = t[p].l t[p].r>>1;
if(l<=mid)change2(p*2,l,r,z);
if(r>mid)change2(p*2 1,l,r,z);
t[p].pre = (t[2*p].pre t[2*p 1].pre)%mod;
}
ll query(int p,int l,int r){
if(l<=t[p].l&&r>=t[p].r){
return t[p].pre%mod;
}
spread(p);
ll ans = 0;
int mid = t[p].l t[p].r>>1;
if(l<=mid)ans =query(p*2,l,r),ans%=mod;
if(r>mid)ans =query(p*2 1,l,r),ans%=mod;
return ans;
}
int main()
{
int n, m;
scanf("%d%d%lld", &n, &m, &mod);
for(int i=1; i<=n; i ){
scanf("%lld", &a[i]);
}
build(1, 1, n);
while(m--){
int chk;
scanf("%d", &chk);
int x, y;
ll k;
if(chk==1){
scanf("%d%d%lld", &x, &y, &k);
change2(1,x,y,k);
}
else if(chk==2){
scanf("%d%d%lld", &x, &y, &k);
change1(1,x,y,k);
}
else{
scanf("%d%d", &x, &y);
printf("%lldn", query(1,x,y));
}
}
return 0;
} 
