Link. 有附加内容。懒得搬了。

最喜欢的一集。

题目的要求十分简洁，但是贡献的计算非常繁琐诡异，而 $n$ 非常小。基本上可以直接放弃别的想法直奔网络流了。

观察一下贡献的形式，发现 $d_{i, j}$ 的贡献方式是我们熟悉的，可以用最大权闭合子图的模型来描述。所以考虑一下最小割。

除了 $d_{i, j}$ 我们还有一个 $mx^2 + cx$ 的贡献。这两个贡献仍然可以看作最大权闭合子图。具体地，选上 $d_{i, i}$ 后会产生 $ma_i^2$  的代价，如果之前已经产生过了则无所谓。给每种类型建一个点即可。

类似地，$cx$ 可以平摊到每次选 $x$ 的位置上，对 $d_{i, i}$ 对应的 $a_i$ 建立点 $A_i$ 并连边，表示选上 $d_{i, i}$ 则必须选上 $-a_i$。

然后就没了。讲一下最大权闭合子图，考虑这样一个模型：给定一张 $n$ 个点 $m$ 条边的有向图。每个点有代价 $a_i$，可正可负。你可以选上一些点，你的分数是你选的点的 $a$ 之和。但是选点有限制，选上一个点 $x$ 则必须选上 $x$ 能到达的所有点。求最大分数。

这个过程可以看作，选一些正权点，为了得到它们的权值不得不割舍一些负权点的代价。

于是考虑转化一下限制，改写成：选一些正权点，选上一个点后必须选上其所能到达的负权点。

这样做的好处在于，即简化了问题，又保证答案不会改变。感觉非常妙。

然后就是最小割建模。建立源汇点 $S, T$，对于每个正权点 $i$，连 $S\to i$，流量为 $a_i$。对于每个负权点 $i$，连 $i\to T$，流量 $-a_i$。对于正权点 $i$ 和其所能到达的负权点 $j$，连边 $i\to j$，流量 $+\infty$。答案即为正权点权值和减去最小割。

显然有一个 $\mathcal O(m\log m)$ 的 LCT 做法：将边按照 $a$ 升序排序，依次加入，动态维护最小生成树，这是 LCT 的经典应用。

那我不会 LCT，又该怎么通过这个题呢？

令人疑惑的是，榜上有大量的神秘复杂度 SPFA 做法，还有评论区中的二分套二分。这显然是错的，事实上不会 LCT 也有对应的常规手段处理。

秉持着 "直接做就好了" 的信念来处理，考虑二分答案转化为判定问题，设二分值为 $mid$。我们要求 $a_{\max} + b_{\max} \le mid$，不好利用判定的优势，于是转化一下，令 $c = mid - b$，那么就是 $a_{\max}\le c_{\min}$。

这个限制可以改写成 $\forall (a, c), a\le c_{\min}\le c$。此时就比较明晰了，使用线段树分治 + 可撤销并查集维护每个 $c_{\min}$ 对应的边，判断是否能形成一棵生成树，如果可行便 check 成功，如果不存在这样的 $c$ 则 check 失败。

时间复杂度 $\mathcal O(m\log^2 m\log n)$。代码也比较好写。

冷静下来想想，这个做法其实是有一些道理的（接下来是自己的碎碎念，并不一定很有意义）。

由 [SDOI2008] 洞穴勘测 我们知道，对于简单的，只含边的加入 / 撤销，判断联通状态，可离线的 LCT 问题，我们可以采用线段树分治 + 可撤销并查集来维护。结合 LCT 维护最小生成树的背景，猜想可以通过一些转化，让条件变成形如 "一条边有少数个存在的范围，判断是否能形成一棵生成树" 这样的问题。

一开始的一些推断告诉我们，直接做不存在好的数学性质，并且只能 LCT 维护，进而想到尝试二分答案转化为相对容易的判定。通过常见手段对限制进行改写，从而使得判定条件中的常数 $mid$ 带来更多作用。结合前面的感觉，得到正确的解法。

COGS 的 G++9.30 评测机还没有好。。。代码就放在 这里 了。由于卡常，代码并不是很可读。

考虑 $k = 1$ 的情况，不妨设 $a$ 降序，此时显然是呈 $\dots, a_4, a_2, a_1, a_3, a_5, \dots$ 状。

然后考虑 $k > 1$，根据数论结论我们知道环长是 $n / \gcd(n, k)$，对于一种环长 $d$，和初始 $k = 1$ 的状态有 $\mathcal O(n / d)$ 处修改，于是记忆化处理，时间复杂度根据调和级数为 $\mathcal O(n\ln n)$。

原神大王系列怎么没有这道题？

考虑把 $(\sum a, \sum b)$ 作为一个生成树的坐标，那么这个点的贡献就是它和原点围成的面积。

这样的问题有一个经典结论是有可能成为答案的点一定构成一个下凸包。

然后有这么一个算法叫 QuickHull。具体地，先求出 $\sum a$ 最小的点 $A$ 和 $\sum b$ 最小的点 $B$，然后找一个离 $A, B$ 最远的点 $C$。$A, B$ 可以直接最小生成树求。

这个条件可以看成 $S_{\triangle ABC}$ 最大化，用向量叉乘的式子画一画发现要最小化 $(x_B - x_A)y_C + (y_A - y_B)x_C$ 加上一堆常量，那令一条边的权值是 $b\times (x_B - x_A) + a\times (y_A - y_B)$ 跑最小生成树即可。当求出来的这个值 $\ge 0$ 的时候说明直线左下方没有点了，停止；否则递归处理 $(A, C), (C, B)$ 之间的情况。

据说这样凸包上点的期望个数是 $\mathcal O((na)^{\frac{2}{3}})$ 个。

view in my blog.

这种背包是 $\max,+$ 卷积，没法支持删除，线段树分治可以做，但是不牛。

考虑双栈模拟，左栈存队列左端，右栈存队列右端，求答案就做一个单调队列滑动窗口。为了代码方便可以把其中一个背包复制一遍，写起来比较舒服。

当一个栈弹空的时候，暴力重构两个栈，也就是把另一个栈的一半信息分过来。

这样做的复杂度如何？考虑势能分析。令势能为两栈大小之差的绝对值，每次增删会产生 $1$ 的势能，而每次重构会花费 $\mathcal O(np)$ 的代价消耗 $n$ 单位的势能。所以复杂度即为 $\mathcal O(mp)$。

考虑倍增。

$f(i,k), g(i,k)$ 分别表示从 $i$ 出发，走 $2^k$ 步经过的边权最小值和边权和。一开始 $f(i,0)=g(i, 0)=w_i$。

为了方便处理，我们定义 $to(i, k)$ 表示从 $i$ 出发，走 $2^k$ 步走到的点。$to(i, k)$ 显然是容易处理的。根据 $to(i, k)$ 预处理 $f(i, k), g(i, k)$ 即可。

时间复杂度 $O(n \log ⁡k )$。