P4513 小白逛公园 线段树
发布日期:2021-09-25 23:58:02 浏览次数:11 分类:技术文章

本文共 1792 字,大约阅读时间需要 5 分钟。

动态维护区间最大子段和
比较简单的一个题吧,复习一下。
让后就是注意读题,存在 x > y 情况。。不判断后面点全部re渍渍渍,痛击不读题的小菜鸡。。之前石油大还做过一个直接题目不给,让后数据存在 x > y 的情况,真是毒瘤了。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)#define pb push_back#define mk make_pairusing namespace std;typedef long long LL;typedef pair
PII;const int N=500010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m;int a[N];struct Node{ int l,r; int mxl,mxr,mx,sum;}tr[N<<2];void push(int u){ tr[u].sum=tr[L].sum+tr[R].sum; tr[u].mxl=max(tr[L].mxl,tr[L].sum+tr[R].mxl); tr[u].mxr=max(tr[R].mxr,tr[R].sum+tr[L].mxr); tr[u].mx=max(max(tr[L].mx,tr[R].mx),tr[L].mxr+tr[R].mxl);}void build(int u,int l,int r){ tr[u]={ l,r}; if(l==r) { tr[u].sum=tr[u].mxl=tr[u].mxr=tr[u].mx=a[l]; return; } build(L,l,Mid),build(R,Mid+1,r); push(u);}void modify(int u,int l,int r,int x){ if(tr[u].l==tr[u].r) { tr[u].sum=tr[u].mxl=tr[u].mxr=tr[u].mx=x; return; } if(l<=Mid) modify(L,l,r,x); else modify(R,l,r,x); push(u);}Node query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) return tr[u]; if(r<=Mid) return query(L,l,r); else if(l>Mid) return query(R,l,r); else { Node x,y; x=query(L,l,r),y=query(R,l,r); Node ans; ans.mxl=max(x.mxl,x.sum+y.mxl); ans.mxr=max(y.mxr,y.sum+x.mxr); ans.sum=x.sum+y.sum; ans.mx=max(max(x.mx,y.mx),x.mxr+y.mxl); return ans; }}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); while(m--) { int op,x,y; scanf("%d%d%d",&op,&x,&y); if(op==1) { if(x>y) swap(x,y); printf("%d\n",query(1,x,y).mx); } else modify(1,x,x,y); } return 0;}/**/

转载地址:https://blog.csdn.net/DaNIelLAk/article/details/108286993 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:CodeForces - 896C 珂朵莉树
下一篇:P3391 文艺平衡树

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年03月05日 02时40分00秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

npm 不重启 全局安装后_解决修复npm安装全局模块权限的问题 2019-04-21
vs格式化json 不生效_vs code 格式化 json 配置 2019-04-21
go 字符串反序列化成对象数组_Fastjson 1.2.24反序列化漏洞深度分析 2019-04-21
onmessage websocket 收不到信息_WebSocket断开重连解决方案,心跳重连实践 2019-04-21
centos命令行安装mysql_CentOS7.6安装MYSQL8.0的步骤详解 2019-04-21
hibernate mysql 缓存_hibernate和mysql的缓存问题,没辙了! 2019-04-21
abp框架 mysql_ABP框架使用Mysql数据库 2019-04-21
mysql树形递归删除_使用递归删除树形结构的所有子节点(java和mysql实现) 2019-04-21
linux mysql 不能连接远程_linux mysql 远程连接 2019-04-21
mysql $lt_mongodb中比较级查询条件:($lt $lte $gt $gte)(大于、小于)、查找条件... 2019-04-21
install python_Install python on AIX 7 2019-04-21
jquery查找div下第一个input_jquery查找div元素第一个元素id 2019-04-21
如何修改手机屏幕显示的长宽比例_屏幕分辨率 尺寸 比例 长宽 如何计算 2019-04-21
mysql 的版本 命名规则_MySQL版本和命名规则 2019-04-21
no java stack_Java Stack contains()用法及代码示例 2019-04-21
java动态代码_Java Agent入门学习之动态修改代码 2019-04-21
python集合如何去除重复数据_Python 迭代删除重复项,集合删除重复项 2019-04-21
iview 自定义时间选择器组件_Vue.js中使用iView日期选择器并设置开始时间结束时间校验功能... 2019-04-21
java 验证码校验_JavaWeb验证码校验功能代码实例 2019-04-21
java多线程初学者指南_Java多线程初学者指南(4):线程的生命周期 2019-04-21