【树形结构】训练题A - Can you answer these queries I
2022/1/25 23:36:30
本文主要是介绍【树形结构】训练题A - Can you answer these queries I,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意
就是要求一个区间的连续的最大字段和
思路
线段树,注意用结构体建树来的会更方便一些
代码
#include<iostream> #include<cmath> #include<stack> #include<map> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #define Endl "\n" typedef long long ll; const int maxn=1e6+5; const int mod=1e9+7; using namespace std; ll N,M,x,y; ll a[maxn]; struct node{ int lmax,rmax,sum,dat; }; struct node tr[maxn<<2]; void up(int p) { tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum; tr[p].lmax=max(tr[p<<1].lmax,tr[p<<1].sum+tr[p<<1|1].lmax); tr[p].rmax=max(tr[p<<1|1].rmax,tr[p<<1|1].sum+tr[p<<1].rmax); tr[p].dat=max(max(tr[p<<1].dat,tr[p<<1|1].dat),tr[p<<1].rmax+tr[p<<1|1].lmax); } void build(int l,int r,int p) { // cout<<"here"<<Endl; if(l==r) { tr[p].lmax=tr[p].rmax=tr[p].sum=tr[p].dat=a[l]; return ; } int m=(l+r)>>1; build(l,m,p<<1); build(m+1,r,p<<1|1); up(p); } node query(int x,int y,int l,int r,int p) { if(x<=l&&y>=r) return tr[p]; int m=(l+r)>>1; if(y<=m) return query(x,y,l,m,p<<1); if(x>m) return query(x,y,m+1,r,p<<1|1); else { node ans,a,b; a=query(x,y,l,m,p<<1); b=query(x,y,m+1,r,p<<1|1); ans.sum=a.sum+b.sum; ans.dat=max(a.dat,a.rmax+b.lmax); ans.dat=max(ans.dat,b.dat); ans.lmax=max(a.lmax,a.sum+b.lmax); ans.rmax=max(b.rmax,b.sum+a.rmax); return ans; } } int main() { cin>>N; for(int i=1;i<=N;i++) cin>>a[i]; build(1,N,1); cin>>M; while(M--) { cin>>x>>y; cout<<query(x,y,1,N,1).dat<<Endl; } return 0; }
这篇关于【树形结构】训练题A - Can you answer these queries I的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享