3 solutions
-
3
有彩蛋
不开
long long见祖宗题意
线段树加法乘法的区改
思路
相信遇到的问题都是如何让加和乘不改变顺序去存储懒标记
先加 再乘的例题, 就是一个分配律
先乘 再加的例题, 就是一个去括号
葱冥德仁救乙晶布庸宰网夏砍乐
加法不改变以前的顺序,只有乘法才会有影响,那么
出现乘法就是 (both)
-
将乘法的懒标记乘上因数
-
将加法的懒标记乘上因数
出现加法就是
- 将加法的懒标记加上加数
要将懒标记还给节点时
- 只要将
tree乘上乘法的懒标记再加上加法的懒标记
细节
记得开
long long,不开long long见祖宗加法懒标记初值为
乘法懒标记初值为 !!!
记得每乘或加一次就要模上模数
代码
#include<iostream> #define int long long //不开 long long 见祖宗 #define N 100005 using namespace std; int n,m,mod; int a[N]; int tree[4*N]; int jf[4*N];//加法的懒标记 int cf[4*N];//乘法的懒标记 int xf(int s,int t,int x) { int m=(s+t)>>1; tree[x*2]=(tree[x*2]*cf[x]+jf[x]*(m-s+1))%mod;//将`tree`乘上乘法的懒标记再加上加法的懒标记 tree[x*2+1]=(tree[x*2+1]*cf[x]+jf[x]*(t-m))%mod; cf[x*2]*=cf[x];//将乘法的懒标记乘上因数 cf[x*2+1]*=cf[x]; //将加法的懒标记乘上因数 //将加法的懒标记加上加数 jf[x*2]=(jf[x*2]*cf[x]+jf[x])%mod; jf[x*2+1]=(jf[x*2+1]*cf[x]+jf[x])%mod; cf[x*2]%=mod; cf[x*2+1]%=mod; cf[x]=1;//变为1 jf[x]=0; return m; } void btree(int l,int r,int x) { cf[x]=1;//这里要注意 if(l==r) { tree[x]=a[l]; tree[x]%=mod; return; } int m=(l+r)>>1; btree(l,m,x*2); btree(m+1,r,x*2+1); tree[x]=tree[x*2]+tree[x*2+1]; tree[x]%=mod; } int gtree(int l,int r,int s,int t,int x) { if(l<=s && t<=r) return tree[x]; int m=xf(s,t,x),sum=0; //新版的检查懒标记方法,同时返回中间的mid if(l<=m) sum+=gtree(l,r,s,m,x*2); if(r>m) sum+=gtree(l,r,m+1,t,x*2+1); return sum; } void uctree(int l,int r,int s,int t,int c,int x)//乘法 { if(l<=s && t<=r) { //不用多说 tree[x]*=c; cf[x]*=c; jf[x]*=c; tree[x]%=mod; cf[x]%=mod; jf[x]%=mod; return; } int m=xf(s,t,x); if(l<=m) uctree(l,r,s,m,c,x*2); if(r>m) uctree(l,r,m+1,t,c,x*2+1); tree[x]=tree[x*2]+tree[x*2+1]; tree[x]%=mod; } void ujtree(int l,int r,int s,int t,int c,int x)//加法 { if(l<=s && t<=r) { //不用多说 tree[x]+=c*(t-s+1); jf[x]+=c; tree[x]%=mod; jf[x]%=mod; return; } int m=xf(s,t,x); if(l<=m) ujtree(l,r,s,m,c,x*2); if(r>m) ujtree(l,r,m+1,t,c,x*2+1); tree[x]=tree[x*2]+tree[x*2+1]; tree[x]%=mod; } signed main() { cin>>n>>m>>mod; for(int i=1;i<=n;i++) cin>>a[i]; btree(1,n,1); while(m--) { int o,x,y,k; cin>>o>>x>>y; if(o==1) { cin>>k; uctree(x,y,1,n,k,1); } else if(o==2) { cin>>k; ujtree(x,y,1,n,k,1); } else cout<<gtree(x,y,1,n,1)%mod<<"\n"; } return 0; }彩蛋
送上猎奇歹马
#include<iostream> #define N 100005 #define int long long using namespace std; int n,m,mod; int a[N]; int tree[4*N]; int jf[4*N]; int cf[4*N]; int clazy(int s,int t,int x)//***看不懂吧 { int m=(s+t)>>1; tree[x<<1]=(tree[x<<1]*cf[x]+jf[x]*(m-s+1))%mod; tree[x<<1|1]=(tree[x<<1|1]*cf[x]+jf[x]*(t-m))%mod; cf[x<<1]=(cf[x<<1]*cf[x])%mod; cf[x<<1|1]=(cf[x<<1|1]*cf[x])%mod; jf[x<<1]=(jf[x<<1]*cf[x]+jf[x])%mod; jf[x<<1|1]=(jf[x<<1|1]*cf[x]+jf[x])%mod; cf[x]=1,jf[x]=0; return m; } void btree(int l,int r,int x) { cf[x]=1; if(l==r) tree[x]=a[l]%mod; if(l==r) return; int m=(l+r)>>1; btree(l,m,x<<1); btree(m+1,r,x<<1|1); tree[x]=(tree[x<<1]+tree[x<<1|1])%mod; } int gtree(int l,int r,int s,int t,int x) { if(l<=s && t<=r) return tree[x]; int m=clazy(s,t,x),sum=0; if(l<=m) sum+=gtree(l,r,s,m,x<<1); if(r>m) sum+=gtree(l,r,m+1,t,x<<1|1); return sum; } void uctree(int l,int r,int s,int t,int c,int x) { if(l<=s && t<=r) { tree[x]=(tree[x]*c)%mod; cf[x]=(cf[x]*c)%mod; jf[x]=(jf[x]*c)%mod; return; } int m=clazy(s,t,x); if(l<=m) uctree(l,r,s,m,c,x<<1); if(r>m) uctree(l,r,m+1,t,c,x<<1|1); tree[x]=(tree[x<<1]+tree[x<<1|1])%mod; } void ujtree(int l,int r,int s,int t,int c,int x) { if(l<=s && t<=r) { tree[x]=(tree[x]+c*(t-s+1))%mod; jf[x]=(jf[x]+c)%mod; return; } int m=clazy(s,t,x); if(l<=m) ujtree(l,r,s,m,c,x<<1); if(r>m) ujtree(l,r,m+1,t,c,x<<1|1); tree[x]=(tree[x<<1]+tree[x<<1|1])%mod; } signed main() { cin>>n>>m>>mod; for(int i=1;i<=n;i++) cin>>a[i]; btree(1,n,1); while(m--) { int o,l,r,k; cin>>o>>l>>r; if(o!=3) { cin>>k; if(o==1) uctree(l,r,1,n,k,1); if(o==2) ujtree(l,r,1,n,k,1); } else cout<<gtree(l,r,1,n,1)%mod<<"\n"; } return 0; }-
C23huangminzhe @ 2024-12-18 16:33:19
黑体字翻译：聪明的人就已经不用再往下看了
字体教程：不开long long见祖宗
<font color="颜色">文本</font>
-
0
C23zhuanghaojun
LV 6
@ 2024-12-19 13:23:01
#include <bits/stdc++.h> #define int long long using namespace std; int n,q,m; struct str{ int l,r,v,add,mul; }tr[400005]; int a[100005]; void pushup(int p){ tr[p].v=(tr[p<<1].v+tr[p<<1|1].v)%m; } void pushdown(int p){ int mid=(tr[p].l+tr[p].r)>>1; tr[p<<1].v*=tr[p].mul; tr[p<<1].v%=m; tr[p<<1].mul*=tr[p].mul; tr[p<<1].mul%=m; tr[p<<1].add*=tr[p].mul; tr[p<<1].add%=m; tr[p<<1|1].v*=tr[p].mul; tr[p<<1|1].v%=m; tr[p<<1|1].mul*=tr[p].mul; tr[p<<1|1].mul%=m; tr[p<<1|1].add*=tr[p].mul; tr[p<<1|1].add%=m; tr[p<<1].v+=tr[p].add*(mid-tr[p].l+1); tr[p<<1].v%=m; tr[p<<1].add+=tr[p].add; tr[p<<1].add%=m; tr[p<<1|1].v+=tr[p].add*(tr[p].r-mid); tr[p<<1|1].v%=m; tr[p<<1|1].add+=tr[p].add; tr[p<<1|1].add%=m; tr[p].mul=1; tr[p].add=0; //繁琐的pushdown } void build(int p,int x,int y) { tr[p].l=x; tr[p].r=y; tr[p].add=0; tr[p].mul=1; if(x==y) { tr[p].v=a[x]; return; } int mid=(x+y)>>1; build(p<<1,x,mid); build(p<<1|1,mid+1,y); pushup(p); } //建树 void update_mul(int p,int x,int y,int k) { if(x<=tr[p].l&&tr[p].r<=y) { tr[p].v*=k; tr[p].v%=m; tr[p].mul*=k; tr[p].mul%=m; tr[p].add*=k; tr[p].add%=m; return; } pushdown(p); int mid=(tr[p].l+tr[p].r)>>1; if(x<=mid){ update_mul(p<<1,x,y,k); } if(y>mid){ update_mul(p<<1|1,x,y,k); } pushup(p); } //上传乘法 void update_add(int p,int x,int y,int k) { if(x<=tr[p].l&&tr[p].r<=y) { tr[p].v+=k*(tr[p].r-tr[p].l+1); tr[p].v%=m; tr[p].add+=k; tr[p].add%=m; return; } pushdown(p); int mid=(tr[p].l+tr[p].r)>>1; if(x<=mid){ update_add(p<<1,x,y,k); } if(y>mid){ update_add(p<<1|1,x,y,k); } pushup(p); } //上传加法 int query(int p,int x,int y) { if(x<=tr[p].l&&tr[p].r<=y){ return tr[p].v; } pushdown(p); int mid=(tr[p].l+tr[p].r)>>1; int ans=0; if(x<=mid){ ans+=query(p<<1,x,y); } if(y>mid){ ans+=query(p<<1|1,x,y); } return ans%m; } //查询 signed main() { ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>q>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } build(1,1,n); for(int i=1;i<=q;i++){ int f; cin>>f; if(f==1){ int x,y,k; cin>>x>>y>>k; update_mul(1,x,y,k); } if(f==2){ int x,y,k; cin>>x>>y>>k; update_add(1,x,y,k); } if(f==3){ int x,y; cin>>x>>y; cout<<query(1,x,y)<<"\n"; } } } -
0
-
C23lvzekai
@ 2024-12-18 16:30:10
怎么没加载出来内容呀
-
C23panweiming
LV 8
@ 2024-12-14 21:27:56
- 1
