BZOJ 1798, 維護(hù)序列

2019-11-09 20:20:59

字體：大中小

來(lái)源：轉(zhuǎn)載

供稿：網(wǎng)友

PRoblem

傳送門

Mean

維護(hù)一個(gè)數(shù)列，要求支持區(qū)間加、區(qū)間乘以及查詢操作。

Analysis

很裸的線段樹(shù)，難點(diǎn)在于加法和乘法的操作順序。標(biāo)記下傳時(shí)應(yīng)先打乘法標(biāo)記，再打加法標(biāo)記，同時(shí)更新時(shí)還要用乘法標(biāo)記維護(hù)加法標(biāo)記。

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