存档【线段树】 本是古典 何须时尚 2024-03-17 17:32 36阅读 0赞 存一下写到一般的线段树 呃呃 [1008-数据结构\_2021秋季算法入门班第十一章习题:线段树、树状数组 (nowcoder.com)][1008-_2021_ _nowcoder.com] #include <bits/stdc++.h> #define int long long using namespace std; const int mxn=1e5+10; const int mxe=1e5+10; const int mod=1e9+7; const int Inf=1e18; struct info{ int sum; }; info operator+(const info &l,const info &r){ info res; res.sum=l.sum+r.sum; return res; } struct tag{ int add,mul; }; struct Segtree{ info val; tag t; }tree[mxe<<2][3]; //1为区间和,2为区间平方和 int N,M,op,l,r,x; int a[mxn]; void pushup(int rt){ tree[rt][1].val=tree[rt<<1][1].val+tree[rt<<1|1][1].val; tree[rt][2].val=tree[rt<<1][2].val+tree[rt<<1|1][2].val; } void settag1(int rt,int tot){ } void settag2(int rt,int tot){ } void pushdown(int rt,int tot){ for(int i=1;i<=2;i++){ if(tree[rt][i].t.add!=0||tree[rt][i].t.mul!=1){ if(i==1){ settag1(rt<<1,tot-tot/2); settag1(rt<<1|1,tot/2); }else{ settag2(rt<<1,tot-tot/2); settag2(rt<<1|1,tot/2); } tree[rt][i].t.add=0; tree[rt][i].t.mul=1; return; } } } void build(int rt,int l,int r){ if(l==r){ //tag tree[rt][1].t.add=tree[rt][2].t.add=0; tree[rt][1].t.mul=tree[rt][2].t.mul=1; //val tree[rt][1].val.sum=a[l]; tree[rt][2].val.sum=a[l]*a[l]; return; } int mid=l+r>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); pushup(rt); } void modify(int rt,int l,int r,int x,int y,int k,int mode){ if(x<=l&&r<=y){ if(mode==1){ //区间加 settag1(rt,r-l+1); //1 tree[rt][1].val.sum+=k*(r-l+1); //2 tree[rt][2].val.sum=tree[rt][2].val.sum+2*k*tree[rt][1].val.sum+(r-l+1)*k*k; }else{ //区间乘 settag2(rt,r-l+1); //1 tree[rt][1].val.sum*=k; //2 tree[rt][2].val.sum*=k*k; } return; } pushdown(rt,r-l+1); int mid=l+r>>1; if(x<=mid) modify(rt<<1,l,mid,x,y,k,mode); if(y>mid) modify(rt<<1|1,mid+1,r,x,y,k,mode); pushup(rt); } info query(int rt,int l,int r,int x,int y,int mode){ if(x<=l&&r<=y){ if(mode==1){ return tree[rt][1].val; }else{ return tree[rt][2].val; } } pushdown(rt,r-l+1); int mid=l+r>>1; if(x>mid) return query(rt<<1|1,mid+1,y,x,y,mode); else if(y<=mid) return query(rt<<1,l,mid,x,y,mode); else{ return query(rt<<1,l,mid,x,y,mode)+query(rt<<1|1,mid+1,r,x,y,mode); } } void solve(){ cin>>N>>M; for(int i=1;i<=N;i++) cin>>a[i]; build(1,1,N); while(M--){ cin>>op; if(op==1){ cin>>l>>r; cout<<query(1,1,N,l,r,1).sum<<'\n'; }else if(op==2){ cin>>l>>r; cout<<query(1,1,N,l,r,2).sum<<'\n'; }else if(op==3){ cin>>l>>r>>x; modify(1,1,N,l,r,x,2); }else{ cin>>l>>r>>x; modify(1,1,N,l,r,x,1); } } } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int __=1;//cin>>__; while(__--)solve();return 0; } [1008-_2021_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/26896/1008
相关 存档【线段树】 存一下写到一般的线段树 呃呃 [1008-数据结构\_2021秋季算法入门班第十一章习题:线段树、树状数组 (nowcoder.com)][1008-_2021_ _now 本是古典 何须时尚/ 2024年03月17日 17:32/ 0 赞/ 37 阅读
相关 线段树 [http://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464583.html][http_www.cnblogs.com_s 迈不过友情╰/ 2022年09月20日 09:13/ 0 赞/ 245 阅读
相关 线段树 Ⅱ 单点修改(内容有升级) \[hdu2795\] ([http://acm.hdu.edu.cn/showproblem.php?pid=2795][http_acm.hdu 朴灿烈づ我的快乐病毒、/ 2022年08月03日 13:45/ 0 赞/ 266 阅读
相关 线段树 线段树:一棵完全二叉树,每个节点代表一个区间。 关于单点更新: \[hdu1166 \] ([http://acm.hdu.edu.cn/showproblem.php?p ﹏ヽ暗。殇╰゛Y/ 2022年08月03日 13:45/ 0 赞/ 246 阅读
相关 线段树 线段树详解 By 岩之痕 目录: 一:综述 二:原理 三:递归实现 四:非递归原理 五:非递归实现 六:线段树解题模型 七:扫描线 八: 你的名字/ 2022年07月14日 00:08/ 0 赞/ 272 阅读
相关 线段树 线段树入门: 转载博客:[点击打开链接][Link 1] 前几天开始接触线段树,其一些基本的操作还是很容易理解的,但是区间更新我着实理解了好一会(因该是本人太菜),今天有时 Myth丶恋晨/ 2022年05月29日 22:16/ 0 赞/ 303 阅读
相关 线段树 一 概述 线段树,类似区间树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的复杂度为O(l 川长思鸟来/ 2022年05月17日 05:53/ 0 赞/ 288 阅读
相关 线段树 线段树(单点修改) 1 include <bits/stdc++.h> 2 using namespace std; 3 4 stru 亦凉/ 2021年12月03日 07:17/ 0 赞/ 352 阅读
相关 线段树 转载 [https://www.cnblogs.com/TheRoadToTheGold/p/6254255.html][https_www.cnblogs.com_TheRo 心已赠人/ 2021年07月16日 15:21/ 0 赞/ 492 阅读
还没有评论,来说两句吧...