线段树进阶
0x01 李超线段树
FZPJ4519 [2021冬令营模拟] 上古遗迹
【题目背景】
“沙……沙……沙……”独行者的脚步一次次被刻进沙漠中，干冷的风携沙尘在男子的四围穿过。
“该死……这沙尘什么时候才能消停会儿……”男子止不住地咳嗽，随即停了下来，开始查看便携式投影设备上的信息，“应该就在附近了才对……”
就在这时，风尘似乎是要止住，又仿佛是无意地，将不远处那方遗迹显现出来。
【题目描述】
ConneR 所寻找的遗迹是一排高耸的石板。这排石板总共由 \(n\) 块宽度均为 \(1\) 并且无缝隙地竖直矗立在地面上的石板组成，其中从左到右数的第 \(i\) 块石板高度为 \(h_i\)。例如下图是 \(n = 5\) 时这些石板可能的样子（图中每个小正方形面积为 \(1\)）：
ConneR 想要在石板上采集到尽可能多的信息，但他发现自己的信息采集装置的电量只够他采集一块矩形区域的石板信息了。同时，由于信息采集装置的设计缺陷，该装置采集的矩形区域必须是完整的。
ConneR 可以选择采集左下角 \(3 \times 3\) 的一块矩形的信息（下图的红色部分），但不能选择采集左下角一块 \(3 \times 4\) 的矩形的信息，因为第 \(4\) 块石板高度只有 \(2\)。
ConneR 想要问你他在这个遗迹上最大可以采集到多大面积的信息。同时，由于风沙影响了 ConneR 的行动范围，ConneR 会给出你多组询问，每次询问他在一个区间的石板上最多能采集到多大面积的信息。
对于所有测试点，满足 \(1 \le n, m \le 2 \times 10^5，1 \le h_i \le 10^9，1\le l\le r\le n\)。
FZOJ4116 [2020省选模拟] 网络运输
今天Nick来到了一个大公司(CCF)，这个公司掌控了整个城市的运输系统，这个运输系统在各种运输线的连接下形成了一个网状结构。
当然，任何系统都会有缺陷，这个系统的缺陷在于所有的运输线都会有一定的延时，一共有 \(n\) 种运输线，相同种类的运输线延时是相同的。
由于每天会有很多的货物需要通过这个网络进行运输，所以管理员小J需要制订每天的运输计划，当然，他就需要知道某个货物从生产地运送到某个运输站的最短延时。
为了简化问题，假设所有货物的生产地在 \(0\) 号运输站，所有的运输站形成了一个分层结构，第 \(1\) 层有 \(n\) 个运输站，第 \(2\) 层有 \(n-1\) 个运输站……第 \(n\) 层有 \(1\) 个运输站，小J用 \((i,j)\) 表示第 \(i\) 层的第 \(j\) 个运输站，注意 \(i \le j \le n\)，因为第 \(2\) 层没有第 \(1\) 个运输站，第 \(3\) 层没有第 \(1,2\) 个运输站，以此类推。这个网络的结构比较奇怪。\(0\)号运输站通过一条\(j\)类型的单向运输线与 \((1,j)\) 相连；当 \(i \gt 1\) 时，运输站 \((i-1,j-1)\) 和运输站 \((i-1,j)\) 通过两条 \(j\) 类型的单向运输线与运输站 \((i,j)\) 相连。对于所有 \(i \ge 1\)，货物只能够从第 \(i-1\) 层向第 \(i\) 层运输。
令天有 \(m\) 个货物需要运输，小T想要知道每个货物到达目的地的最短延时，他找到了Nick帮忙，由于Nick没带电脑，所以这个光荣而艰巨的任务就交给你啦！
\(100\%\)的数据：$n,m \le 10^5,0 \le p_i \le 20000, 1 \le x'_i,y'_i \le n $。
FZOJ4725 [2021NOI模拟] 小 H 的树上序列
小 H 有一棵 \(n\) 个点的树，每个点有点权 \(a_i\)。
小 H 不喜欢树，但他喜欢序列，于是他在树上选择了一个点对 \((x,y)\)，并将从 \(x\) 到 \(y\) 的简单路径上的节点的点权按经过顺序排序，形成一个序列。
小 H 认为，每个序列都应该有其美观度。小 H 定义序列 \(\{b_k\}\) 的美观度为 \(\sum_{i=1}^k\sum_{j=1}^ib_j\)。
小 H 想知道，在他的树上，选择哪一个点对，能使得到序列的美观度最大。请你帮助他解决这个问题。
\(n\leq 1.5 \times 10^5,a_i\leq 10^6\)。
P2305 [NOI2014] 购票
今年夏天，NOI 在 SZ 市迎来了她三十周岁的生日。来自全国 \(n\) 个城市的 OIer 们都会从各地出发，到 SZ 市参加这次盛会。
全国的城市构成了一棵以 SZ 市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 \(n\) 个城市用 \(1\sim n\) 的整数编号。其中 SZ 市的编号为 \(1\)。对于除 SZ 市之外的任意一个城市 \(v\)，我们给出了它在这棵树上的父亲城市 \(f_v\) 以及到父亲城市道路的长度 \(s_v\)。
从城市 \(v\) 前往 SZ 市的方法为：选择城市 \(v\) 的一个祖先 \(a\)，支付购票的费用，乘坐交通工具到达 \(a\)。再选择城市 \(a\) 的一个祖先 \(b\)，支付费用并到达 \(b\)。以此类推，直至到达 SZ 市。
对于任意一个城市 \(v\)，我们会给出一个交通工具的距离限制 \(l_v\)。对于城市 \(v\) 的祖先 A，只有当它们之间所有道路的总长度不超过 \(l_v\) 时，从城市 \(v\) 才可以通过一次购票到达城市 A，否则不能通过一次购票到达。
对于每个城市 \(v\)，我们还会给出两个非负整数 \(p_v,q_v\) 作为票价参数。若城市 \(v\) 到城市 A 所有道路的总长度为 \(d\)，那么从城市 \(v\) 到城市 A 购买的票价为 \(dp_v+q_v\)。
每个城市的 OIer 都希望自己到达 SZ 市时，用于购票的总资金最少。你的任务就是，告诉每个城市的 OIer 他们所花的最少资金是多少。
对于所有数据，\(n\leq 2 \times 10^5, 0 \leq p_v \leq 10^6,\ 0 \leq q_v \leq 10^{12},\ 1\leq f_v<v,\ 0<s_v\leq lv \leq 2 \times 10^{11}\)，且任意城市到 SZ 市的总路程长度不超过 \(2 \times 10^{11}\)。
P4069 [SDOI2016] 游戏
Alice 和 Bob 在玩一个游戏。
游戏在一棵有 \(n\) 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 \(123456789123456789\)。
有时，Alice 会选择一条从 \(s\) 到 \(t\) 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 \(r\)，若 \(r\) 与 \(s\) 的距离是 \(dis\)，那么 Alice 在点 \(r\) 上添加的数字是 \(a\times dis+b\)。
有时，Bob 会选择一条从 \(s\) 到 \(t\) 的路径。他需要先从这条路径上选择一个点，再从那个点上选择一个数字。
Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。
对于所有数据，\(n \leq 100000\)，\(m \leq 100000\)，$ | a | \leq 10000 $，\(0\le w, |b|\le 10^9\)。
UOJ#423 【集训队作业2018】万圣节的积木
建筑需要整体结构来维持，不能只靠地基…… —— LazyJazz
[万圣节Party进行时……]
LazyJazz号召大家一起来搭积木，搭一座巨高巨高的积木塔。大家一起先构思了一个最终目标，即最终塔的形状，然后打算分工搭出若干小积木塔，每个小积木塔对应最终塔的某一段结构，最后一个一个摞起来。
积木塔的最终形态由 \(n\) 块密度均匀且相等，宽、高相等，长度不定的积木上下摞在一起，宽对齐，从上至下数第 \(i\) 块积木覆盖了横坐标对应 \(L_i\) 至 \(R_i\) 的范围（包含 \(L_i\) , \(R_i\) 两点），长度为 \(R_i - L_i\) 单位长度。根据前面的描述，可以得出结论，每块积木的质量正比于其长度。
由于是积木塔，所以塔有可能不稳定，稳定的判定条件是：若一个积木塔有 \(m\) 层，当且仅当对于任意 \(i∈[1,m)\) ，从上至下数，前 \(i\) 块积木的重心落在第 \(i+1\) 块积木的覆盖范围内，则稳定，否则不稳定。前 \(i\) 块积木的重心为前 \(i\) 块积木的几何中心，以质量为权重的带权平均位置。
例如:
一个 \(3\) 层的积木塔，从上到下，第一层覆盖范围为 \([1,3]\),第二层覆盖范围为 \([0,2]\),第三层覆盖范围为 \([1,2]\)，其结构是稳定的。
.##
##.
.#.一个 \(3\) 层的积木塔，从上到下，第一层覆盖范围为 \([1,3]\),第二层覆盖范围为 \([0,2]\),第三层覆盖范围为 \([0,1]\)，其结构是不稳定的（即便每两层分开看都稳定）。
.##
##.
#..一个 \(3\) 层的积木塔，从上到下，第一层覆盖范围为 \([0,8]\),第二层覆盖范围为 \([4,12]\),第三层覆盖范围为 \([5,7]\)，其结构是稳定的（即便最底下两层看上去不稳定）。
########....
....########
.....##.....LazyJazz想要把塔搭好，又要避免中间过程出现不稳定结构（即最终积木塔分解成的一段一段的小积木塔都稳定，且在一个一个摞小积木塔时的所有中间形态也都稳定），所以需要聪明的你帮忙提前规划好该如何把最终结构拆成小积木塔结构，保证拆解后层数最多的小积木塔层数最小。你只需要回答拆解后层数最多的小积木塔层数最小是多少即可。
CF1178G The Awesomest Vertex
\[\left| \sum_{w \in R(v)} a_w \right| \cdot \left| \sum_{w \in R(v)} b_w \right| \]给定一棵根为 \(1\) 的有根树，每个节点有两个权值 \(a[i]\) 和 \(b[i]\) 。定义 \(R(v)\) 为 \(v\) 祖先的集合（包括自己），则一个节点 \(v\) 有多棒取决于其真棒程度，真棒程度是这样定义的：
标签：10,le,进阶,积木,省选,城市,运输,2024,leq From： https://www.cnblogs.com/Alston-Wan/p/17856521.html\(|x|\) 表示 \(x\) 的绝对值。
现在请你支持两种操作：
● \(1 \ \ v \ \ x\) — 将 \(a_v\) 加上 \(x\)
● \(2 \ \ v\) — 输出以 \(v\) 为根的子树中最大的真棒程度
\(1≤n≤2⋅10^5,1≤q≤10^5\)，\(-5000≤a_i≤5000,-5000≤b_i≤5000\)，$ 1\leq x \leq 5000$。