B. 一棵树
首先有个暴力 dp，设 \(f_{i,j}\) 表示在 \(i\) 子树内选了 \(j\) 个的最小值，转移是平凡的。
然后发现这玩意是凸的，于是可以直接上 slope trick。
但是涉及到合并两个序列，直接平衡树启发式合并是 \(O(n\log ^2n)\) 的。但是你会发现，我们只需要维护前 \(\frac{k}{2}\) 和后 \(\frac{k}{2}\) 即可，因此可以用两个可并堆维护。时间复杂度 \(O(n\log n)\)，常数不大。
C. 前缀和
\(y_i\) 的组合意义是有无穷多个灯，第 \(i\) 个灯以 \(p\) 的概率亮，\(1-p\) 的概率不亮，第 \(i\) 个亮的灯的期望位置。
所以有多少个 \(y_i\) 落在 \([l,r]\) 中相当于 \([l,r]\) 中有多少个灯亮着，于是答案是 \((r-l+1)p\)。
D. 多折较差验证
首先有个比较暴力的做法：感觉合法的回文串个数只有 \(O(n\log n)\) 个，区间 DP 暴力转移就是 \(O(n^2\log n)\) 的。
但是 A_zjzj 爆了个标，因为我们发现我们只需要找到最长的可以翻折的地方折进去，对于两问的答案都不会更劣，因此这样做就是 \(O(n^2)\) 的。
I. 分治乘法
std 是四毛子，谁写那个玩意/hsh
考虑直接分治是 \(n\log n\) 步的，算出来大概要 \(10^7\) 大小。我们发现只需要将其除以二就可以卡近限制。
发现分治的过程没有利用第三步操作。考虑当前分治区间 \([l,r]\)，中点为 \(mid\)，如果 \(x\) 与 \(x+(mid-l)\) 都为 \(1\)，则构造出 \(x\) 之后左移一下就可以得到 \(mid-l\)。因此我们可以分成三部分：只有左边有 \(1\) 的，只有右边有 \(1\) 的，以及两边都有的，然后用哈夫曼树合并即可。
这样做我造出来的最大数据也不过 \(4\times 10^6\)，完全能过（
H. 二进制
这里是一个愚蠢的 2log 做法。
先将操作分成 \([2^i,2^{i+1}-1]\) 的 \(\log\) 段，每一段内维护每个对应长度的值有多少个，然后开个堆维护一下就行，这样就是 \(2\log\) 的。
但是我们注意到，在删除之后的重构过程，总共只会往堆中加入 \(O(n)\) 个元素，因此这一部分就是 \(O(n\log n)\) 的，所以瓶颈在于每一块的重构。可以用手写堆，或者把堆换成 set 均可 \(O(n)\) 建树，将复杂度做到 \(O(n\log n)\)。
但是只有一个 2log 的代码（
A. 排序大师
构造需要最小化，通常需要借助图之类的来说明其是最优的。
我们考虑在排列开头加上 \(0\)，结尾加上 \(n+1\)，然后建边 \(p_i+1\to p_{i+1}\)，这样我们发现，我们的最终状态是 \(n+1\) 个环。
假设我们现在操作 \(i,j,k,l\)，那么原来的边是 \(p_{i-1}+1\to p_{i}\)，\(p_{j}+1\to p_{j+1}\)，\(p_{k-1}+1\to p_k\)，\(p_l+1\to p_{l+1}\)。
现在的边是 \(p_{i-1}+1\to p_{k},p_{j}+1\to p_{l+1},p_{k-1}+1\to p_i,p_{l}+1\to p_{j+1}\)>
可以发现，这样的操作的任意性不会强于两次选择两个点，交换其出边。
而选择两个点交换出边只会增加至多 \(1\) 个环，所以，如果我们能每次减少两个环，那么这个交换次数就是顶到下界的。
具体的，我们有如下构造方法：
- 选择最小的点 \(x\)，满足 \(x\) 前面存在一个 \(y>x\)，选择这个 \(y\)。
- 容易说明，\(x-1\) 在 \(y\) 前面，\(y+1\) 在 \(x\) 后面，因此将 \(x\) 换到 \(x-1\) 前面， \(y\) 换到 \(y+1\) 后面即可增加两个自环。
时间复杂度 \(O(n^2)\)。