由于我太懒了，所以就不每题开一篇写了。题目大意也懒得写了。
显然最优策略是瞎走，在知道那条边断掉了之后才走最短路径。
先把以 \(T\) 为根的最短路树求出来，然后可以用堆求出断掉每条边后端点到 \(T\) 的最短路径。
最后像 dijk 那样 DP 一下就好了。
直接线段树 + 凸包优化 DP 可以轻松做到 \(O(n\log n)\)
用 这个方法 可以优化到 \(O(n)\)
不同的环长只有 \(O(\sqrt n)\) 种。
对每种环长算一下答案即可。
直接缩个点然后每个出度为 \(0\) 的连通块扔掉最小值即可。
用 这个东西，用平衡树维护序列即可。
如果可以修改一个 \(a_i\) 满足 \(\forall i,a_{i+1}<a_i+b_i or a_{i+1}>a_i+c_i\)，那么那一个人第一天就会发现。
如果可以修改两个，那么那两个人第二天都会发现。
现在就是要修改最少的 \(a_i\) 满足上面那个东西。
可以 DP。枚举上一个没有修改的 \(j\)，那么要求 \([a_i-B_{i-1},a_i-C_{i-1}]\subseteq[a_j-B_{j-1},a_j-C_{j-1}]\)。其中 \(B,C\) 分别是 \(b,c\) 的前缀和。
可以发现区间长度是单调的。
然后按 \(a_i-B_{i-1}\) 排序求个 LIS 即可。
直接重链剖分然后在重链上二分是 \(O(n\log^2n)\) 的。
在重链上从下往上的求轻子树的答案。
当遇到一个轻子树答案为 \(0\) 时，这条链上面的答案就都是 \(0\) 了。
这样就只用二分下面那部分了。
复杂度应该是 \(O(n\log n)\) 的。
先二分答案 \(s\)。
弄一个网格，把 \(a_i+b_j\leq s\) 的部分染白，剩下的部分染黑。
那么就是你一开始在 \((1,1)\)，每次找一个同行或同列的异色的点走过去。
如果 \((1,1)\) 在所有最大匹配上，那么先手必胜。
然后把最大匹配换成最大独立集。
把 \(a_i,b_j\) 排序后，选的一定是 \(i\leq R,j\leq C\)的白色部分和 \(i>R,j>C\) 的黑色部分。
可以发现，当 \(R\) 变大的时候，\(C\) 变大的收益是单调的，\(C\) 也是单调的。
直接扫一遍就好了。
先让每个点能匹配 \(k\) 条边跑一边网络流。
然后每次把度数 \(=\) 度数最大值得点找出来，找一个覆盖这些点的匹配。
重复 \(k\) 次即可。
记 \(f_{i,j}\) 为长度为 \(i\)，zjt 在 \(j\) 处的期望答案。
显然 \(f_{i,1}=f_{i,i}=i\)
设 \(f_{3,2},f_{4,2},\ldots,f_{m,2}\) 这 \(m-2\) 个未知数，每次可以通过 \(f_{i,j}\) 推出 \(f_{i+1,j+1}\) 的式子。
最后把 \(f_{m,2},f_{m,3},\ldots,f_{m,m-1}\) 这 \(m-1\) 个式子拿出来消元即可。
分块分类讨论或者树套树都能过。
对于每一个 \(i\leq n\)，新建一个点 \(i'\)。
连边 \((i,i')\)
对于每一组 \((i,j)\)，连边 \((i',j)\)
答案为最大匹配 \(-n\)。
用一棵平衡树维护当前所有最优解以及最优解的答案
每次遇到一个新的 \(a_i\) 时，先把当前所有最优解的答案加上 \(a_i\) 的贡献。
还有一种情况，就是最优解到 \(a_i\) 时值为 \(a_i-1\)。
那就拿之前的最优解平移一下即可。
这样就能找到之前所有位置都做了最优操作的解（如果不是最优操作，就不会成为最大值）。
可以发现，最优解的 \(C\) 一定是 \(P-w_i-1\) 或 \(T\)。
把这些值拿出来每个二分答案 DP 一下就是 \(O(n^2(-\log \epsilon))\) 的了。
这个做法的瓶颈在于二分答案。
但是我们可以把这些 \(C\) 值 shuffle 一下，每次遇到一个 \(C\) 就 \(O(n)\) 判断答案是否大于上一个，大了再二分，这样就只用求 \(O(\log n)\) 次答案了。
复杂度是 \(O(n^2+n\log n(-\log \epsilon))\)
可以发现，\(f(a_1,a_2,\ldots,a_n)=2^{n-1}(a_1 or a_2 or\cdots or a_n)\)
然后 \(n>2\) 的答案和 \(n=2\) 的答案是相同的。
然后人类智慧手玩一下就好了。
按颜色的出现次数分块分类讨论就好了。
原文：https://www.cnblogs.com/ywwyww/p/10671098.html