AGC049F 更优秀的做法

题面

给定长度为 \(n\) 的整数序列 \(A\)，\(B\) 和 \(C\)。snuke 是开心的，当且仅当下面的条件满足：

• 对于任意整数 \(x\)，均有 \(\sum_{1 \le i \le n} |A_i - x| \le \sum_{1 \le i \le n} |B_i - x|\)。

他决定改变 \(A\) 中的一些元素来变得开心。把 \(A_i\) 改成 \(t\) 需要花费 \(C_i \times (A_i-t)^2\) 的代价。其中，\(t\) 必须得是整数。

为了使 snuke 变得开心，至少要花费多少代价呢？

数据范围：\(1 \le n \le 2 \times 10^5\)，\(0 \le A_i,B_i,C_i \le \color{red}{10^9}\)。

题解

首先考虑维护 \(g(x) = \sum_i |a_i-x| - \sum_i |b_i-x|\)。最后的要求就是 \(g(x) \le 0\)。

可以把 \(A_i,B_i\) 看成数轴上的点。对于一个 \(A_p = x\)，将 \(A_p\) 改成 \(y(y \ge x)\) 的过程可以看成是不停地把 \(A_p\) 往右移。每次对 \(A_p\) 的移动 \(i \to i+1(i \ge A_p)\)，相当于是给 \(x \le i\) 的 \(g(x)\) 增加 \(1\)，给 \(x > i\) 的 \(g(x)\) 减少 \(1\)。其代价为 \(C_p(2i-2A_p+1)\)。

注意到 \(x \to x+1\) 和 \(x+1 \to x+2\) 中，后者增加的代价更大，而前者的操作优于后者。因此虽然我们要求执行完 \(x \to x+1\) 后才能执行 \(x+1 \to x+2\)，但是事实上把他们独立开来仍然是正确的。减小的操作是对称的。

又注意到如果有操作 \(u \to u-1\)，和操作 \(v \to v+1\)，那么必然有 \(u-1 \ge v+1\)：如果不满足条件，则把两个操作都删了肯定更优秀。

这就意味着存在一个分界线 \(mid\)，使得只有 \(u > mid\) 的 \(u \to u-1\) 操作和 \(v<mid\) 的 \(v \to v+1\) 操作。在这里，如果存在多个 \(mid\)，选择 \(g(mid)\) 最大的那个。

然后可以发现，操作后必然满足 \(g(mid)=0\)。这是因为，我们找到 \(mid\) 左边第一个向右的操作，和 \(mid\) 右边的第一个操作，同时删去他们，答案一定变小（由于奇偶性，\(g(mid) \neq 1\)）。

观察到所有操作都让 \(g(mid)\) 减小了，这说明 \(mid\) 是被操作最多的元素。而由于操作后 \(g(mid) = 0\)，说明 \(g(mid)\) 是操作后最大的元素。减的最多，结果最大，说明 \(g(mid)\) 初始时就是最大的！因此我们就能够找到 \(mid\) 了。

找到后，考虑把问题分成左右两部分，左边增加，右边减小。而两边中唯一会影响另一边的因素是两边的操作次数。

带入 \(g(-\infty)\) 和 \(g(\infty)\) 可知 \(\sum a_i = \sum b_i\)，因此我们可以知道两边操作个数的差。我们又知道两边操作次数的和：总和为 \(g(mid)\)。这样就可以解出来两边的操作次数。因此两部分就是完全独立的了。更具体地，两边操作后均满足 \(\sum a_i = \sum b_i\)。

所以现在我们的问题就转化成了一个只有增加的问题了。

二分一个斜率 \(M\)，然后执行所有代价 \(\le M\) 的操作。每个点移动到了一个新点，我们从把每个点都看成从新点出发移动。

注意到改成从新点移动后，之前的大部分结论都还是是成立的！也就是说，这里同样存在一个 \(mid\)，使得之后做的操作，\(mid\) 左边的只向右，\(mid\) 右的只向左。\(mid\) 仍然满足 \(g(mid)\) 是最大的。我们仍然可以按照 \(mid\) 把数轴切成两半，两半互不相关！

注意到切完之后，两边操作的代价范围都减半了，因此不停地做一些类似整体二分的东西，递归下去即可！

时间复杂度 \(\Theta(n \log n (\log A + \log B + \log C))\)。

aclink。