Aizu 2450 Do use segment tree 树链剖分
2024-09-06 10:00:12
题意:
给出一棵\(n(1 \leq n \leq 200000)\)个节点的树,每个节点有一个权值。
然后有\(2\)种操作:
- \(1 \, a \, b \, c\):将路径\(a \to b\)上的所有点的权值都变为\(c\)
- \(2 \, a \, b \, c\):查询路径\(a \to b\)的权值和最大的非空连续子序列
分析:
首先要树链剖分,将问题转为线性的问题:
给出一个序列,查询给定区间\([L,R]\)的最大非空连续子序列。
线段树最重要的一点就是可以由左右子区间的合并得到父亲节点的区间信息。
这里维护区间的四个信息:
- \(sum\):就是区间的所有元素和
- \(pre\):区间的最大前缀和
- \(suf\):区间的最大后缀和
- \(sub\):区间的最大子区间和,也正是题目所求的
区间合并可以这样合并:
- \(sum_f=sum_l+sum_r\)
- \(pre_f=max \{ pre_l, sum_l + pre_r \}\),最大前缀可能在左子区间,可能跨过区间中点
- \(suf_f=max \{ suf_r, suf_l+sum_r \}\),最大后缀可能在右子区间,可能跨过区间中点
- \(sub_f=max \{ sub_l, sub_r, suf_l+pre_r \}\),最大子区间可能在左子区间,可能在右子区间,也可能跨过区间中点,就是左子区间的最大后缀与右子区间的最大前缀拼接起来
然后再将问题转移到树上,就是简单的一段一段的区间合并就行了。
注意区间合并的方向,查询的时候是将两个顶点向着\(LCA\)往上跳,注意最后合并的时候将区间翻转一下。
最后如果默认将节点\(1\)作为根节点开始\(DFS\)的话会爆栈,所以我们将\(\left \lceil \frac{n}{2} \right \rceil\)作为根就可以了。
这么鸡贼的做法,我猜肯定是出过题的人想出来的
最新文章
- WordPress酷炫CSS3读者墙代码
- 【Linux】df命令 ,查看磁盘容量。
- 安卓手机屏幕录像之scr
- opencv2学习:计算协方差矩阵
- WPF 得到子指定元素方法和得到指定子元素集合方法MvvM得到焦点
- TCP/IP详解学习笔记(12)-- TCP:传输控制协议
- 栈帧%ebp,%esp详解
- oracle 不转义 &;
- 关于DDOS攻击中TCP半连接数与FD的关系
- CentOS 7 安装MySql Server 5.6
- 谷歌浏览器js debug
- Azure Messaging-ServiceBus Messaging消息队列技术系列5-重复消息:at-least-once at-most-once
- [js高手之路] html5 canvas教程 - 绘制七巧板
- 【mongodb系统学习之十】mongodb查询(一)
- git 学习(3) ----- 代码共享和多人协作
- Java基础 【自动装箱和拆箱、面试题】
- RPG难题
- C# 同一应用程序域不同线程之间的参数传递方式
- 必须记住的 30 类 CSS 选择器
- ARKit从入门到精通(1)-ARKit初体验