20220927测试总结
0927考试总结
T1
题意超级钢琴。
真的是非常经典的题目了，可以说是开创了处理同一个问题 \(1-k\) 优解的先河。
将解空间拆分成二维，枚举其中一维，考虑第二维的选择并计算答案，用
priority_queue
选择最优答案，选择答案后将当前的第一维按第二维剩下的情况拆分。
动态点分治也是一样的思路。
T2
非常经典的题目，严格递增转不降是经典套路，最优解一定取到每个数值也是经典结论。
本题保证数据随机，应该是需要利用随机序列单调上升子序列长度为 \(O(\sqrt n)\) 的性质，但实际上可以 \(O(n^2)\) 轻松通过。
哦，应该是考虑补集转化，然后考虑哪些点固定，然后 \(dp_i\) 表示第 \(i\) 个点固定的最优代价，转移只能从能完成
LIS
转移的点转移过来，中间合法的条件是要么大于右边要么小于左边，根据经典结论一定可以调整成一段和左边相等，一段和右边相等，然后随机的情况下转移点个数
\(O(1)\)，长度 \(O(\sqrt n)\)，总复杂度 \(O(n\log n+n\sqrt n)\)。
简单证明经典结论
假设有一种最优解包含了不是原有数的数。
考虑第一个不是原有数的数，如果它被调大了，那么把它调小成上一个原有数一定更优。
如果它被调小了，就把它调到第一个比调整后的数大的原有数的位置，如果因此导致后面若干个数小于它了，那么不难得知这些数现在都被夹在两个原有的数之间，而且都是从两个原有数区间的外面调整过来的。从左边第一个数开始，找和它相同的数，如果相同的数中，被调小的数较多，那么全部调到第一个和它不同的数，否则调回第一个原数，变成子问题。
T3
最大值最小显然二分。
考虑一个划分合法的条件，发现只能在某些合法的位置断开，而且在这些位置是否断开不影响第一个条件的合法性。
所以考虑对这些位置动态规划，直接转移是 \(O(n^2)\) 的，然后考虑维护所有可能的转移，发现如果拿个单调栈记录 \(a\)，那么转移的改变可以描述为 \(O(n)\) 次区间加，线段树维护即可。
一个数组，考虑每个前缀的后缀最大值，可以被描述为 \(O(n)\) 次区间加。