线段树的升级操作

前言

既然线段树可以实现加法的区间修改，那能不能实现下乘法的区间修改呢？ 答：当然可以 区间的每个数都乘于k相当于他们的和乘于k，更新时tree[now]*=k即可，同样需要懒标记来维护实现，方法和区间加法的区间修改相似

下面介绍与加法区间修改不同的地方

void init() { for(int i=1; i<=n*4; i++)lazy2[i]=1; } void pushup(int now) { tree[now]=tree[now*2]+tree[now*2+1]; } void pushdown(int now,int l,int r,int mid) { if(lazy[now]>1) { tree[now*2]*=lazy[now]; tree[now*2+1]*=lazy[now]; lazy[now*2]*=lazy[now]; lazy[now*2+1]*=lazy[now]; lazy[now]=1; } } void update_chen(int now,int l,int r,int ql,int qr,int k) { if(ql<=l&&r<=qr) { tree[now]*=k; lazy2[now]*=k; return; } int mid=(l+r)/2; pushdown(now,l,r,mid); if(ql<=mid)update_chen(now*2,l,mid,ql,qr,k); if(qr>mid)update_chen(now*2+1,mid+1,r,ql,qr,k); pushup(now); } int query(int now,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr)return tree[now]; int mid=(l+r)/2,ans=0; pushdown(now,l,r,mid); if(ql<=mid)ans+=query(now*2,l,mid,ql,qr); if(qr>mid)ans+=query(now*2+1,mid+1,r,ql,qr); return ans; }

【注意】乘法通常和mod有关 【拓展】线段树还可实现乘法与除法并用（mod），但仅限于将乘过的数除去，即将乘过的点单点更新为1即可；乘x即将一个点为1的点修改成x P4588数字计算

问题升级

P3373加乘法的线段树

如何同时对区间进行加和乘的操作呢，因为在pushdown的时候要考虑到先加后乘或者是先乘后加，如果没有想办法处理这运算顺序的差异，显然答案是错的。

可以看出最难的部分在pushdown pushdown时，是要先加还是先乘呢？ 答：先乘再加，但要注意，加的值也要变化，即相应的乘 即 (s+k)* t=s* t+k* t 同样：在乘操作时也需要对加的值进行相应的乘

lazy[]存储加，chen[]存储乘 易知chen的初始值为1，lazy的初始值为0，且pushup时重置

完整代码

#include<bits/stdc++.h> using namespace std; #define ll long long const long long N=1e5+10; ll tree[N*4],a[N],lazy[N*4],chen[N*4],n,p,m; void pushup(ll now) { tree[now]=(tree[now*2]+tree[now*2+1])%p; } void pushdown(ll now,ll l,ll r,ll mid) { if(lazy[now]||chen[now]!=1){ tree[now*2]=(tree[now*2]*chen[now]+lazy[now]*(mid-l+1))%p; tree[now*2+1]=(tree[now*2+1]*chen[now]+lazy[now]*(r-mid))%p; //先乘后加原则 lazy[now*2]=(lazy[now*2]*chen[now]+lazy[now])%p; lazy[now*2+1]=(lazy[now*2+1]*chen[now]+lazy[now])%p; //加的值也要相应的乘，且先乘后加 chen[now*2]=chen[now*2]*chen[now]%p; chen[now*2+1]=chen[now*2+1]*chen[now]%p; chen[now]=1; lazy[now]=0; } } void build(ll now,ll l,ll r) { chen[now]=1;//初始值设为1 if(l==r) { tree[now]=a[l]%p; return; } ll mid=(l+r)/2; build(now*2,l,mid); build(now*2+1,mid+1,r); pushup(now); } void update_jia(ll now,ll l,ll r,ll ql,ll qr,ll k) { if(ql<=l&&r<=qr) { tree[now]=(tree[now]+k*(r-l+1))%p; lazy[now]=(lazy[now]+k)%p; return; } ll mid=(l+r)/2; pushdown(now,l,r,mid); if(ql<=mid)update_jia(now*2,l,mid,ql,qr,k); if(qr>mid)update_jia(now*2+1,mid+1,r,ql,qr,k); pushup(now); } void update_chen(ll now,ll l,ll r,ll ql,ll qr,ll k) { if(ql<=l&&r<=qr) { //加的值也要相应的乘 tree[now]=tree[now]*k%p; chen[now]=chen[now]*k%p; lazy[now]=lazy[now]*k%p; return; } ll mid=(l+r)/2; pushdown(now,l,r,mid); if(ql<=mid)update_chen(now*2,l,mid,ql,qr,k); if(qr>mid)update_chen(now*2+1,mid+1,r,ql,qr,k); pushup(now); } ll query(ll now,ll l,ll r,ll ql,ll qr) { if(ql<=l&&r<=qr)return tree[now]; ll mid=(l+r)/2,ans=0; pushdown(now,l,r,mid); if(ql<=mid)ans+=query(now*2,l,mid,ql,qr); if(qr>mid)ans+=query(now*2+1,mid+1,r,ql,qr); return ans%p; } int main() { ll x,y,k,key; cin>>n>>m>>p; for(ll i=1; i<=n; i++)cin>>a[i]; build(1,1,n); for(ll i=1; i<=m; i++) { cin>>key; if(key==1) { cin>>x>>y>>k; update_chen(1,1,n,x,y,k); } if(key==2) { cin>>x>>y>>k; update_jia(1,1,n,x,y,k); } if(key==3) { cin>>x>>y; cout<<query(1,1,n,x,y)<<endl; } } return 0; }