2022.03.30学习记录（wqs二分，四边形不等式）
又来写学习记录啦！
今天一早上起来就开始莫名emo，感觉林克卡特树还是不会什么的。
真的，好烦，好难受。
没事，哼，再怎样才浪费一个小时而已，还有大把的美好时光，好好享受信竞带来的乐趣吧！
而且也不要一emo就开始觉得考不上了什么的，这一个月，只是帮助你奔赴所爱的事物，结果如何，不必太放在心上。作息调整得规律些，休息的时候健康些，自我怀疑也会少一些的。
还有，待办绝不是牢笼，它只是一个辅助你的工具。
另外，周末放松的时候，也可以看点书啊。《说理的境界》、《寂寞圣哲》，之类的。收起电子产品去看。还有还有，晚上睡前看人民日报评论，早上起来背单词，固定10点50睡6点30起，语文英语早读参加，数学物理挑重点听，就这么说定啦。
说定了，去做，一定是不难的，也是最不累、最不内耗的。
于是又浪费了一个小时，狂水游记。
看到wkahpm的历练之路，看到rainy7的心路历程。
现在已经快十点了。
今天好像真的什么都不想干。
但是，不会颓下去的！一定会振作起来的。
冷冷说过，早上要是做成了了不起的事情，一天都可以作为支点呢。
早上明明还有两个小时，怕什么呢？
而且，不是已经在努力学wqs二分和树形dp了吗？
一定可以的。先把wqs二分的入门题打了，再去打林克卡特树吧。
啊，我爱我爸！
跟我爸聊了一小会儿（顺便强行给他灌了一下wqs二分的概念，他认真地嗯嗯嗯，也不知道听懂了没），感觉心结palapala打开了！
来吧，重启完毕，Working Mode On!
今天好好学一下wqs二分。
wqs二分，用于解决形如“限定选k个”的问题。这类问题满足，每多选一个，收益单调递增（下凸包）或收益单调递减（上凸包）且如果去掉限制求最优解，问题就非常好求解。
以上凸包为例，去掉限制求最优解的过程，相当于拿一条斜率为0的直线去切这个凸包，并且可以轻松切到截距最大的点。这时候可以手动调整直线的斜率，直到切到自己想要的点为止。
但是但是，要注意！切到的点所处的线段可能恰好斜率跟这条直线相等。这时候可能永远也无法切到题目要的那个条件，但是，只要确保合法并且到达了二分终点，就可以大胆地将题目的限制条件代入得出答案，而不能说它是无解的。
举个例子，比如说P5633 最小度限制生成树（嘿嘿，另外几条狗都没打过！），咱们可以在排序的时候设置编号为s相关边优先选，这样的话，只要mid >=k，就认为是可行解，这样总能找到我们要的答案！
来吧，水一水练一练例题。
陈小汪卷过！是可忍，孰不可忍？！
来，看一看题目。
题意：给定一条数轴及N个点（1 <= N <= 3000，1 <= pos <= 10000），在P个点（1 <= P <= 300）建立邮局，使得每个村庄与其最近的邮局距离之和最小。
设d[i]表示坐标，pre[i]表示前 i 个村庄的坐标之和，mi[i][j]表示第一个坐标值在i, j坐标中点以后的村庄（可以双指针处理，当然二分一下也行，不是瓶颈）。
能想到的思路：
先考虑暴力dp。我们需要记录三维：
考虑第 i 个村庄一定建邮局，当前已经建了 j 个邮局的代价。
j >= 2: dp[i][j] = min{0 <= k < i}
( dp[k][j - 1]
- ((pre[i] - pre[mi[k][i] - 1]) * 2 - (i - mi[k][i] + 1) * (d[i] + d[k])) （中点以后的村庄）
- (n - i) * (d[i] - d[k]) ) （此村庄之后的村庄）
j == 1:dp[i][j] = (i * d[i] - pre[i]) + (pre[n] - pre[i] - (n - i) * d[i])
这样我们就写出了一个n三方的暴力dp。
好像有一个优化思路是四边形不等式，有机会了解一下——不过，现在我们的目标是掌握wqs二分。
所以想一想wqs二分怎么优化这个dp。
感性理解一下，每添加一个邮局，减少的代价应该是单调不增的。所以，限定建i个邮局及其对应的最小代价g(i)应该构成下凸包。
再想想，如果没有限制建几个邮局呢？
嘿，那不就是n方的dp。直接把最后一维删掉就好了。
但是，还有一个问题：怎么控制多出来的这些代价？
我们似乎可以二分出一个建邮局的代价。这样，我们切出来的截距f(i) = g(i) + mid * i，dp的时候记一下当前建了几个邮局，真正的答案再扣掉代价即可。
显然，建邮局的代价越高，就倾向于建少一些的邮局——少了降低代价，多了提高代价即可。
没看题解想出来的，打一下试试
30pts WA + TLE
注意，wqs二分中求出的是截距，还原要带原来的
50pts MLE + TLE？
看了一下题解，发现自己的求解sb了
应该是放在中位数的位置 微笑
又看了一眼
一定要用四边形不等式优化！
好吧，转战四边形不等式
针对形如
F[i] = min{F[j] + val(j, i)} (0 <= j < i) 的式子
若val(j, i)满足四边形不等式，则可以采用此优化方法
若定义在整数域上的函数f(i, j)满足：
对于任意a <= b <= c <= d
都有 f(a, d) + f(b, c) >= f(a, c) + f(b, d) ①
或对于任意a <= b
都有f(a, b + 1) + f(a + 1, b) >= f(a, b) + f(a +1, b + 1) ②
则称其满足四边形不等式
②式证明：
若a < b，令a + 1 = a代入②得
f(a + 1, b + 1) + f(a + 2, b) >= f(a + 1, b) + f(a + 2, b + 1) ③，
② + ③相消得
f(a, b + 1) + f(a + 2, b) >= f(a, b) + f(a + 2, b + 1) ④
发现 a + 2 可以类似地换成 (a, b)间的任意一项。故令c = b, b = x∈(a, b)，有
即 f(a, c + 1) + f(b, c) >= f(a, c) + f(b, c + 1) ⑤
再做一次类似变换，可得
f(a, d) + f(b, c) >= f(a, c) + f(b, d) ⑥
⑥ = ①
证毕。
这里的证明用到了数学中同类相消的技巧
定理：
设使得F[i]取到最优解的j为p[i]，若函数满足四边形不等式，则p[i]单调不减（非严格递增）
证明：
F[i] = F[p[i]] + val(p[i], i) ①
对于任意 j ∈ [0, p[i] - 1] 有
j <= p[i] <= i <= i + 1
由于函数满足四边形不等式，故
val(j, i + 1) + val(p[i], i) >= val(j, i) + val(p[i], i + 1) ②
由p[i]的最优性
F[j] + val(j, i) <= F[p[i]] + val(p[i], i) ③
②+③，得
F[j] + val(j, i + 1) <= F[p[i]] + val(p[i], i + 1)
即p[i]之前的所有决策点都不可能使i + 1更优。
证毕。
考虑维护 p 数组。
初始 p 数组全为 0。当我们求出了F[i]的值，尝试把 i 插入 p 数组，看看哪些 i' 有可能用到 i 。
根据决策单调性，新的位置 pos 必然满足：
任意 j < pos 上的 p[j] 对 j 都不比 i 差， 任意 j > pos 同理。
可以用三元组维护。具体而言：
对于 i ，检查队头
while (l < r && q[l].r < i) ++l;
q[l].l = i;直接将队头作为答案
int j = q[l].p;
f[i] = f[j] + w[j][i];而后尝试插入 i
bool Cmp(int a, int b, int x) { return f[a] + val[a][x] <= f[b] + val[b][x]; }
int pos = n + 1;
while (l <= r) {
if (Cmp(i, q[r].p, q[r].l) { pos = q[r].l; --r; continue; } //队尾可以滚蛋咯
if (Cmp(q[r].p, i, q[r].r) break; //我不可能替代任何人了
int p = q[r].p, L = q[r].l, R = q[r].r;
while (L <= R) {
int MID = L + R >> 1;
if (Cmp(i, p, MID)) pos = MID, R = MID - 1;
else L = MID + 1;
}
q[r].r = pos - 1;
break;
}
if (pos <= n) q[++r] = {i, pos, n};其中需要注意Cmp函数，如果有其他的优先条件，则以优先条件为准。
以这道题为例，wqs二分中需要邮局多的优先。所以判断的时候还应该加上邮局的数量 >= 自身。
下面，我们来证明一下这道题函数w(x, y)满足四边形不等式。
定义w(x, y)表示在村庄[x, y]之间新建一个邮局，距离的代价。
我们有递推式：
w(x, y) = 0 (y == x)
w(x, y) = w(x, y - 1) + d[y] - d[x + y >> 1] (y > x)
也即，对于村庄 a <= b
满足 w(a, b + 1) + w(a + 1, b) >= w(a, b) + w(a + 1, b + 1)
拆项，即证明
d[b + 1] - d[(a + b + 1) >> 1] >= d[b + 1] - d[(a + b + 2) >> 1]
即证明
d[x >> 1] <= d[(x + 1) >> 1]
由于d单调不降，所以四边形不等式得证！