等差数列方向
给 \(N\) 棵树，第 \(i\) 棵树的坐标是 \(a_i \ (-M \leq a_i \leq M)\) 。可以花费 \(b_i\) 的代价将 \(a_i\) 修改为任意整数。询问 \(a_1, a_2, \cdots, a_N\) 构成等差数列需要的最小代价。
思路：
若 \(a_1, a_2, \cdots, a_N\) 是等差数列，则 \((i, a_i)\) 在二维空间上落在一条直线 \(y = A_1 + (d - 1)x = c + kx\) 上，且 \(k = 0 \vee 1 \mid k\) 。
由于 \(f(x) = c x^{0} + k x^{1}\) 是 \(deg\) 为 \(1\) 的多项式，根据插值理论或线性代数理论，可以用两个点确定。
一个经典的 trick 是： 直线经过至少一个点一定比不经过点更优。
-
如果以两点式处理，则直线经过两个点比经过一个点和经过更多点更优。
-
或者以点斜式处理，只需枚举一个斜率，且经过一个点。
方向一：
从两点式考虑。
我们可以 \(O(N^{2})\) 枚举两个点，然后计算这两个点对应直线的贡献。
可以借助直线的一般式 \(Ax + By + C = 0\) （一般是需要约分）维护直线，用 \(\{(A, B, C), value\}\) 表示每条直线上点的 \(b_i\) 贡献和。
答案就是 \(\sum b_i - max\{value\}\) ，时间复杂度 \(O(N^{2} \log N^{2})\) 。
方向二：
从点斜式考虑。
重新确定 \(a\) 数组是从 \(0\) 编号的，即 \(a\) 数组为 \(a_0, a_1, a_2, \cdots, a_{N - 1}\) 。这样可以让第一个点在 \(y\) 轴上，方便点斜式的讨论。
我们考虑一条过 \((0, -M)\) 的直线 \(f(x) = -M + kx\) 。
我们可以取直线过另一个点 \((1, M), (2, M), (3, M), \cdots, (N - 1, M), (N - 1, M - 1), (N - 1, M - 2), \cdots, (N - 1, -M)\) ，初步有 \(0 \leq k \leq 2M\) 。
又注意到等差数列构成的直线，斜率要么是 \(0\) ，要么是 \(1\) 的倍数。则 \(k = 0\) 或者 \(1 \leq k \leq 2M\) 。
由于答案直线过 \((0, A)\) 且 \(A \geq -M\) ，则在 \(f(x)\) 下面的所有点一定要改，而可能要改的是严格在 \(f(x)\) 上方的点，不妨称这些点为有效点。
\(k = 0\) 时可以维护键值对 \((y, value)\) ，对所有存在的 \(a_i\) 权值，计算对应的若干点的 \(b_i\) 贡献。时间复杂度 \(O(N \log N)\) 。
所以只需考虑 \(1 \leq k \leq 2M\) 。
不难发现直线 \(f(x)\) 经过点 \((i, -M + ki)\) ，而有效点是一段前缀满足 \(-M + ki \leq M\) 。继而有 \(\forall i, i \leq \lfloor \frac{2M}{k} \rfloor\) 的点为有效点。
由
\[\sum_{k = 1}^{2M} \lfloor \frac{2M}{k} \rfloor < \sum_{k = 1}^{+\infty} \frac{2M}{k} \leq 2M \ln 2M = O(M \log M) \]显然有效点的个数为 \(O(M \log M)\) ，同时每个有效点可以根据点斜式确定一条直线。
现在考虑答案直线 \(l = A_0 + k(i - 1)\) ，\(l\) 经过一个点会更优，可以枚举所有有效点作为一个固定点。
假设此时的枚举的斜率是 \(k\) ，枚举的固定有效点是 \(a_i\) ，则 \(A_0 + k(i - 1) = a_i \Rightarrow A_0 = a_i - k(i - 1)\) 。
可以维护键值对 \(\{(A_0, k), value\}\) ，对每个固定点计算它对对应直线的 \(b_i\) 贡献。
获得贡献最大的直线 \(l = A_0 + k(i - 1)\) ，是需要修改贡献最少的直线。
最后我们让这根直线和 \(O(N)\) 跳斜率为 \(0\) 的直线取更优值。
总时间复杂度为 \(O(M \log M)\) 。
等比数列方向
给 \(N\) 棵树，第 \(i\) 棵树的坐标是 \(a_i (0 \leq a_i \leq M)\) 。可以花费 \(b_i\) 的代价将 \(a_i\) 修改为任意非负整数。询问 \(a_1, a_2, \cdots, a_N\) 构成等比数列需要的最小代价。
这里限定为正数是因为非初等函数的处理非常困难。
思路：
若 \(a_1, a_2, \cdots, a_N\) 是等比数列，则 \((i, a_i)\) 在二维空间上落在 \(y = A_1 q^{x - 1}\) 上。
要么 \(q = 1\) ，\(f(x) = A_1 q^{x - 1}\) 是一条直线，可以通过维护 \((y, value)\) 以 \(O(N \log N)\) 算出这种每个权值的获得的点的 \(b_i\) 贡献。
否则 \(q > 0 \wedge q \neq 1\) 。（题目不需要同时讨论 \(q < 0\) 的情况，因为这很困难）
这时 \(f(x) = A_1 q^{x - 1}\) 并不是一个多项式，不能通过若干个点确定。
但至少是一个通过常函数 \(c\) 乘以指数函数 \(a^{x} \ (a \neq 1 \wedge a > 0)\) 得到的初等函数，是一条简单曲线，依旧具有简单的性质。
这个初等函数首先可以通过一个公比 \(q(q > 0)\) 和一个点 \((1, A_1)\) 确定。
根据经典 trick ， \(f(x) = A_1 q^{x - 1}\) 至少经过一个点最优。
如果曲线真的只经过了一个点，不妨 \(O(N)\) 处理出 \(\sum_{i = 1}^{N} b_i - b_k\) 。
于是接下来考虑经过至少两个点的曲线，这样会使得曲线的样本空间更小，\(q\) 的取值范围也更小。
我们可以 \(O(N)\) 枚举一个点 \((i, a_i)\) 作为定点，然后枚举 \(q\) ，需要保证 \(q^{i - 1} \mid a_i\) 。于是可以计算出 \(A_1 = \frac{a_i}{q^{i - 1}}\) 。
若 \(\forall i \geq 2, a_i < A_1 q^{i - 1}\) ，则这些曲线依旧是只会经过 \((i, a_i)\) 这一个点。这种情况已经被计算过。
它的逆条件是 \(\exists i \geq 2, a_i \geq A_1 q^{i}\) ，曲线可能会经过一个点以上。
\(q \leq \log_{i} \frac{a_i}{A_1} \leq \log_{2} M\) 可以限制出 \(q\) 的范围。于是需要 \(O(N \log M)\) 枚举一条曲线。
对于任意一个定点 \(a_i\) ，我们将记录它对 \((A_1 = \frac{a_i}{q^{i - 1}}, q)\) 的 \(b_i\) 贡献。维护 \(\{(A_1, q), value\}\) 。
这些曲线最后还要和 \(O(N)\) 条只经过一个点的曲线取更优值。
总时间复杂度为 \(O(N \log M)\) 。
标签：直线,一个点,函数,leq,枚举,2M,取点,初等,log From： https://www.cnblogs.com/zsxuan/p/18331231