由 ryz 讲解
什么是分治？
- 把一个较大规模的问题分成若干个较小规模的问题。
-
小规模的问题与原问题不同（根号分治）
-
小规模的问题与原问题相同（对数分治）
二分就是一种对数分治的方法。
操作序列分治
cdq 分治
修改和询问的整体分治也被称为 cdq 分治。
要求：修改对询问具有可加性
主要操作：
-
将所有操作离线
-
对于区间 \([l,r]\)，选取中点 \(mid\)，只统计左修改对右的贡献
-
递归 \([l, mid], [mid + 1, r]\)
无题号 函数
三种操作，加入一个一次函数，删除一个函数，求 \(x_g\) 处所有函数的最大值，\(n\le 10^6\)。
第一眼看上去是线段树分治（），但是要求用 cdq 做。
考虑维护一个下凸壳，插入好做，删除不好做
考虑把删除改成增加，倒着扫，从 \(r\rightarrow mid + 1\)，用平衡树维护下凸壳。
- 如何用平衡树维护下凸壳
注意到斜率是单增的，考虑维护这个东西。
他肯定是包含了一个斜率区间，然后切掉了两端直线的部分
那么我们维护两个东西：凸包上的斜率，交点的 \(x\) 坐标
然后平衡树找到斜率之后，直接向前向后枚举被删除掉的斜率，维护这两个东西就行
