ATC & CF 选做(23Jul,23Aug)
CF1856 - CFR890ψ(｀∇´)ψ
久违的 CF round 了。
CF1856A Tales of a Sortψ(｀∇´)ψ
可以注意到因为大小关系是偏序关系，我们只需要考虑两个相邻的位置。
换句话说考虑每对 \((i, i + 1) \text{ s.t. } a_i > a_{i + 1}\)，我们算一下达到贡献需要多少。
然后最后求和就行了，这个显然是对的。
CF1856B Good Arraysψ(｀∇´)ψ
考虑尽量用小的数构造，先让 \(b\) 每个都是 \(1\)。
然后考虑切掉 \(a\) 剩下的部分进行调整即可。
CF1856C To Become Maxψ(｀∇´)ψ
手完样例可以发现一定存在一个峰值，旁边的部分是递减。
注意到数据范围是 \(1000\)，考虑直接对每个位置二分答案，取 max 即可。
CF1856D More Wrongψ(｀∇´)ψ
这类交互题有一个常见套路，维护答案集合，考虑删去来做1。
首先答案一定是整体的极值点，我们不妨考虑通过询问逆序对的方式来找到这些极值点的大小关系并维护。
每次考虑答案集合中的两个差最小的元素 \(a_i, a_j\)。
询问 \([i, j]\) 之间的逆序对，如果 \(a_i > a_j\)，这说明 \(inv([i, j]) - inv([i + 1, j]) = j - i\)，我们删除 \(j\)，否则 \([i + 1, j]\) 中一定存在一个比 \(i\) 更大的，不可能为 \(i\)，我们删除 \(i\)。
开始的时候先所有都问一遍，花费为 \(n\)。
然后的询问花费应该为 \(2\sum(\dfrac{n}{i})^2\)，总花费就满足要求。
CF1856E1 PermuTree (easy version)ψ(｀∇´)ψ
注意到我们不大关心相对位置关系，如果考虑在 LCA 处计算贡献，我们只关心数量大小关系。euclidean
一个结论：如果我们考虑两个子树，LCA 处的贡献最大一定是 \(siz_0 \times siz_1\)。
这个结论可以扩展到多个子树，于是我们考虑在每一层对子树的 \(siz\) 作为元素进行可行性背包，每次 check 一下就好了。
但是我不会证明，现在看一下。
根据树形背包复杂度结论，这个实际上也是在枚举两个子树合并，且状态大小和子树大小线性相关，那么复杂度是 \(O(n^2)\) 的。
CF1856E2 PermuTree (hard version)ψ(｀∇´)ψ
我们考虑对 E1 部分的 dp 进行一个优化。
可以注意到，E1 部分的 dp 时间复杂度和子树 size 相关。
于是我们很容易想到使用 dsu on tree 来优化这个过程，减小时间复杂度。
具体来说我们拉出来两个最大的子树，单独考虑。
剩下的部分就是轻子树，根据结论总数为 \(n \log n\) 级别。
这部分用单调队列暴力 dp 即可。
算下来复杂度是逆天的 \(O(n \log n \sqrt{n \log n})\)。
不过后面根号下那一坨，似乎是很难卡满的，感觉可以近似看作一个 \(O(n \log n)\) 带一个常数。
时限 3s，跑的还挺快，比某些人的 bitset 所谓正解快多了。
赛时想到了这个做法不过当时不知道轻子树这个结论，后面赛后翻到 @zltzlt 博客才发现的。
不过当时我猜这个常数巨大没敢写，愤怒，愤怒，柚子你说得对，爱拼才会赢。