《算法竞赛进阶指南》0x43线段树 单点修改+查询区间最大子段和
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了《算法竞赛进阶指南》0x43线段树 单点修改+查询区间最大子段和,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1901字,纯文字阅读大概需要3分钟。
内容图文
![《算法竞赛进阶指南》0x43线段树 单点修改+查询区间最大子段和](/upload/InfoBanner/zyjiaocheng/1189/0d713903f7574d3b9f466314ff0cec0c.jpg)
题目链接:https://www.acwing.com/problem/content/246/
线段树合并线段的时候要更新结点中的ans值,但是这个值的更新依赖于lmax与rmax,这两个值的更新又依赖于sum,故查询的时候需要返回的是一个结点,返回代表的区间的信息。
代码:
#include<iostream> #include<cstdio> usingnamespace std; constint maxn = 500010; constint inf=0x3f3f3f3f; int n,m; struct node{ int l,r,s,lx,rx,ans; }t[maxn*4]; void pushup(int rt){ t[rt].lx=max(t[rt<<1].lx,t[rt<<1].s+t[rt<<1|1].lx); t[rt].rx=max(t[rt<<1|1].rx,t[rt<<1|1].s+t[rt<<1].rx); t[rt].s=t[rt<<1].s+t[rt<<1|1].s; t[rt].ans=max(max(t[rt<<1].ans,t[rt<<1|1].ans),t[rt<<1].rx+t[rt<<1|1].lx); } void build(int rt,int l,int r){ t[rt].l=l; t[rt].r=r; if(l==r){ scanf("%d",&t[rt].ans); t[rt].lx=t[rt].rx=t[rt].s=t[rt].ans; return ; } int mid=l+r>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); pushup(rt); } void update(int rt,int pos,int C){ if(t[rt].l==t[rt].r){ t[rt].s=t[rt].lx=t[rt].rx=t[rt].ans=C; return; } int mid=(t[rt].l+t[rt].r)>>1; if(pos<=mid) update(rt<<1,pos,C); else update(rt<<1|1,pos,C); pushup(rt); } node query(int rt,int L,int R){ if(t[rt].l>=L && t[rt].r<=R){ return t[rt]; } node ans1,ans2; int mid=(t[rt].l+t[rt].r)>>1; if(L<=mid && R>mid){ ans1=query(rt<<1,L,R); ans2=query(rt<<1|1,L,R); node ans; ans.s=ans1.s+ans2.s; ans.lx=max(ans1.lx,ans1.s+ans2.lx); ans.rx=max(ans2.rx,ans2.s+ans1.rx); ans.ans=max(max(ans1.ans,ans2.ans),ans1.rx+ans2.lx); return ans; }elseif(L>mid){ return query(rt<<1|1,L,R); }elseif(R<=mid){ return query(rt<<1,L,R); } } int main(){ cin>>n>>m; build(1,1,n); while(m--){ int t,x,y; scanf("%d%d%d",&t,&x,&y); if(t==1){ if(x>y)swap(x,y); printf("%d\n",query(1,x,y).ans); }elseif(t==2){ update(1,x,y); } } return0; }
原文:https://www.cnblogs.com/randy-lo/p/13297168.html
内容总结
以上是互联网集市为您收集整理的《算法竞赛进阶指南》0x43线段树 单点修改+查询区间最大子段和全部内容,希望文章能够帮你解决《算法竞赛进阶指南》0x43线段树 单点修改+查询区间最大子段和所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。