CDQ 分治，李超树与斜率优化

P4027，及一类类似问题：

给定 \(a_i,b_i,x_i,y_i\)，对于每个 \(i\) 求出 \(f_i = \max\limits_{j=1}^{i} \{a_ix_j+b_iy_j\}\)

先说一下一类经典问题的做法：

给定 \(n\) 个二维向量，多次给定一个向量，求该向量与开始给定向量点乘 / 叉乘最大值。

点乘可以交换两维数值后取反第一维以转化为叉乘。现在来讨论叉乘。

叉乘的几何意义是两向量张出平行四边形的有向面积，取询问向量 \(x\) 作为底，则要找到到给定向量的投影距离（生造一个词 qwq）最小的向量。

找出凸包，则用平行 \(x\) 的直线切凸包，切到的点则是最优点。这是 wqs 二分的内容（？

感性理解，给定向量的斜率单调变化时，切点也单调变化。于是若斜率有序，可以维护一个指针做到均摊 \(O(1)\)。

说回原题，把式子写成 \(\begin{bmatrix} x_j \\ y_j \end{bmatrix} \cdot \begin{bmatrix} a_i \\ b_i \end{bmatrix}\) 即 \(\begin{bmatrix} -y_j \\ x_j \end{bmatrix} \times \begin{bmatrix} a_i \\ b_i \end{bmatrix}\) 的形式，就能化回上述形式。

但是，现在要一边插入一边查询，插入在首位时可以使用单调队列维护，插入在中间只能用平衡树维护。码量太大了，不想学。

在具有时间轴时，cdq 分治允许在离线的条件下，通过一些处理，使得让按其他维度排序成为现实。

现在单来考虑左区间往右区间贡献的部分。此时是一个离线问题，把左边的点插进凸包，右边的点按询问斜率的顺序排序，这样即有序。

（没学过 cdq，下面来随便口胡一下）

一类问题后面的计算依赖前面的计算（分治 fft），感觉上（是的，我在口胡）是把贡献拆成了 \(\log\) 个小区间分别贡献。数轴上共有 \(n \log n\) 个小区间，每个数被包含于 \(\log\) 个小区间中，要给 \(\log\) 个区间贡献。这些说明了复杂度是 \(O(\text{解决一次贡献的复杂度} \cdot \log n)\)。

考虑批量转移，一个区间内的点对后面的一个区间做贡献，这样，被贡献的点之间是独立的，也就让对另一个维度排序成为可能。

一个点需要被它前面的 \(\log\) 个区间转移到，这是一段前缀，不妨进行二进制拆分，每一步拆出最多能拆出的二进制位，那么一个区间 \([i,i+2^k)\) 对 \([i+2^k,i+2^{k+1})\) 批量产生贡献。