考虑构造一道毒瘤题，它拥有 T1 的时间复杂度分析，T2 的数学推导，T3 的代码难度，T4 的卡常。

T1 往事成风

algorithm:segtree

结论题，下面给出三个结论：

  1. 在最优划分中，每个区间的众数都是不同的，否则显然可以合并到一起减小答案。

  2. 若不考虑编号的限制，我们将某些数字选为最后的众数。若这个方案合法，没有被选为众数的数的个数的最大值一定小于等于选出的众数的个数之和。

    这样我们可以得到一个朴素算法，对于每次询问，从高位向地位枚举，如果将当前数字删去后仍满足条件，则删去。最后保留的数字即为众数。

  3. 设 \(V\) 为值域,所有删去的数字形成的连续段数量级为 \(O(\sqrt{V})\)。（我不会证）

考虑优化朴素算法，我们在线段树上删除连续段： 1. 若删去当前节点最小值仍不满足，直接返回。 2. 若将右子树删除满足条件，删去它并遍历左节点。 3. 否则先遍历右子树，再遍历左子树。

T2 数数乐（eval）

algorithm:math

\[ f(n)=\sum_{k=0}^n 2^{n-k}\sum_{m=0}^k \binom{k}{m}\binom{k-m}{\lfloor\frac{k-m}{2}\rfloor}2^{m} \]

设 \(g(k)=\sum_{m=0}^k \binom{k}{m}\binom{k-m}{\lfloor\frac{k-m}{2}\rfloor}2^{m}\)，不难发现只要求出所有 \(g(k)\) 题目就做完了。

而容易得到 \(g(n)=\binom{2n+1}{n}\)（之后会证明这个式子），因此可以做到 \(\mathcal O(\max n+T)\) 的复杂度。

证明？不会。

T3 走廊

algorithm:binary,bst

考虑对 \(2n\) 个路径分别维护一条链。

用平衡树维护分裂合并，用二分找到点就可以了。

T4

暂缺