推歌：早安大森林
模拟赛乱写（你猜我欠了多少。
-
确实是好玩的题。
考虑先将其分成两组，一组 \(<\frac k2\)，一组 \(\ge\frac k2\)
考虑使一个数在填的时候使所以剩余数都可以填它旁边，或都不可以。
可以将每个 \(<\frac k2\) 的数对应其最小可以放的 \(\ge\frac k2\) 的数，然后从大往小放 \(\ge\frac k2\) 的数，每次放完后将所有与它对应的数都一块放了。
-
考虑其本质是求虚树大小。
考虑一个点在虚树内有两个限制：
-
\(u\) 子树内存在至少一个属于序列区间的点。
-
除 \(u\) 子树外其他点和 \(u\) 构成的子树内至少存在一个属于序列区间的点。
发现满足第一个限制但不满足第二个限制是好求的，直接求区间 \(lca\) 即可。
考虑用满足 \(1\) 的减掉满足 \(1\) 且不满足 \(2\) 的点。
对于满足 \(1\) 的点，考虑离线，扫描线可以维护右端点。新加一个点，就对其到根的路径染上当前颜色，最后统计颜色在 \([l,r]\) 之间的点个数即可。
染色可以珂朵莉，统计用树状数组就行。
-
-
这是逆天状态的 \(dp\)
和逆天读题考虑求 \(r\) 轮中第 \(i\) 段被修复的概率。
考虑转移，发现其之和有几次水流到过有关，所以设 \(dp_{i,j}\) 表示前 \(i\) 个位置，在 \(r\) 轮中修复了 \(j\) 次的期望。
\(dp\) 枚举当前是否修过转移，然后就都可以直接推了。
-
trick 猫树分治。
考虑类似猫树，每次对分割点左右进行处理，查询可以直接合并。
发现空间不太够，可以将其离线，对在哪一层排序，只维护一层信息即可。
-
记一下 Kaguya 发现的将 \(\log\) 换成 \(\alpha\) 的做法。
首先对询问分块，每块先将这块之前的修改改掉，对于块内的修改，每次查询时暴力跑一遍，在撤销即可。
用可撤销并查集维护，可以干到 \(n\sqrt n \log n\) 。
考虑前缀的时间排序，可以直接归并，将 \(\log n\) 乘在 \(n\) 上，调整块长可以做到 \(n\sqrt{n \log n}\)
考虑整一下并查集，发现可以路径压缩，对于块内的询问，最多一次完全展开是 \(\sqrt n\) 最多 \(n\) 次，不会有复杂度问题。而加边查询的 \(\log\) 就变成了 \(\alpha\)，复杂度 \(n\sqrt{n \alpha(n)}\)。
但因为常数问题，其实很难跑过带 \(\log\) 做法。
-
树上启发式合并板子。
考虑每次数组维护重儿子信息，轻儿子跑暴力即可。
线段树合并在 CF 上也能过，学校 OJ 跑不过去。
-
发现其就是维护凸壳。
考虑凸壳性质，其差分序列不降，可以直接跑 \(dp\)。
设 \(dp_{i,j}\) 表示用 \(i\) 个正数，和为 \(j\)，因为差分不降，所以最少是 \(\sum\limits_{k=1}^i k=j\)，\(i\) 是 \(\sqrt m\) 级的。
因为有非负限制，考虑枚举最小值的最左边位置，钦定最小值为 \(0\)，最后在平移。
左边长度是定值，右边是一个 \(\le k\) 的限制，用前缀和做掉，平移也可以用前缀和。
时空都带根号，用撤销空间可以省掉根号。
没有鲜花可以不写，不要写这种东西脏了我的眼
