国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁(yè) > 學(xué)院 > 開發(fā)設(shè)計(jì) > 正文

BZOJ 1798, 維護(hù)序列

2019-11-10 18:00:49
字體:
來(lái)源:轉(zhuǎn)載
供稿:網(wǎng)友

PRoblem

傳送門

Mean

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

Analysis

很裸的線段樹,難點(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;}
上一篇:日期類

下一篇:Codeforces 100726A 或 POJ 3842

發(fā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 彭州市| 武川县| 乌拉特中旗| 张家口市| 永寿县| 邵阳县| 高台县| 澜沧| 会同县| 景洪市| 广灵县| 南部县| 安塞县| 大英县| 绵竹市| 尉氏县| 溧阳市| 湘西| 南澳县| 奈曼旗| 乐至县| 唐海县| 雅江县| 余庆县| 南郑县| 包头市| 买车| 玉田县| 新野县| 定南县| 青海省| 景泰县| 怀仁县| 棋牌| 盐亭县| 徐水县| 镇安县| 扎鲁特旗| 息烽县| 息烽县| 环江|