BZOJ 1798, 维护序列

2019-11-09 20:20:59

字体：大中小

来源：转载

供稿：网友

PRoblem

传送门

Mean

维护一个数列，要求支持区间加、区间乘以及查询操作。

Analysis

很裸的线段树，难点在于加法和乘法的操作顺序。标记下传时应先打乘法标记，再打加法标记，同时更新时还要用乘法标记维护加法标记。

Code

#include<cstdio>typedef long long ll;const int N=100005;int n,p,m,x,y,z,cmd,a[N],sum[N<<2],add[N<<2],tag[N<<2];void read(int &x){ char c; while((c=getchar())<'0' || c>'9'); x=c-'0'; while((c=getchar())>='0' && c<='9') x=x*10+c-'0';}void up(int o){sum[o]=(sum[o<<1]+sum[o<<1|1])%p;}void down(int o,int l,int r){ if(l==r) return; int ls=o<<1,rs=o<<1|1,mid=l+r>>1; if(tag[o]!=1){ sum[ls]=(ll)sum[ls]*tag[o]%p; sum[rs]=(ll)sum[rs]*tag[o]%p; tag[ls]=(ll)tag[ls]*tag[o]%p; tag[rs]=(ll)tag[rs]*tag[o]%p; add[ls]=(ll)add[ls]*tag[o]%p; add[rs]=(ll)add[rs]*tag[o]%p; tag[o]=1; } if(add[o]){ (sum[ls]+=add[o]*ll(mid-l+1)%p)%=p; (sum[rs]+=add[o]*ll(r-mid)%p)%=p; (add[ls]+=add[o])%=p,(add[rs]+=add[o])%=p; add[o]=0; }}void build(int o,int l,int r){ if(l==r){sum[o]=a[l];return;} int mid=l+r>>1; build(o<<1,l,mid),build(o<<1|1,mid+1,r); tag[o]=1; up(o);}void update(int o,int l,int r,int ql,int qr,int c,int q){ down(o,l,r); if(ql<=l && r<=qr){ if(q) (sum[o]+=(add[o]=c)*ll(r-l+1)%p)%=p; else{sum[o]=sum[o]*ll(tag[o]=c)%p;add[o]=add[o]*(ll)c%p;} return; } int mid=l+r>>1; if(ql<=mid) update(o<<1,l,mid,ql,qr,c,q); if(qr>mid) update(o<<1|1,mid+1,r,ql,qr,c,q); up(o);}int query(int o,int l,int r,int ql,int qr){ down(o,l,r); if(ql<=l && r<=qr) return sum[o]; int tot=0,mid=l+r>>1; if(ql<=mid) (tot+=query(o<<1,l,mid,ql,qr))%=p; if(qr>mid) (tot+=query(o<<1|1,mid+1,r,ql,qr))%=p; return tot;}int main(){ read(n),read(p); for(int i=1;i<=n;i++) read(a[i]); build(1,1,n); read(m); while(m--){ read(cmd),read(x),read(y); if(cmd==1){ read(z); update(1,1,n,x,y,z,0); }else if(cmd==2){ read(z); update(1,1,n,x,y,z,1); }else printf("%d/n",query(1,1,n,x,y)); } return 0;}

上一篇：振兴中华

下一篇：Leetcode 207. Course Schedule

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注