Codeforces Round 862 (Div. 2)
E. There Should Be a Lot of Maximums
题意：定义一棵点有颜色的树的 \(\text{MAD}\) 为树上编号最大的出现了至少两次的颜色。对于树上每条边，求出断开它后生成的两棵树的 \(\text{MAD}\) 的最大值。\(n\le2\times10^5,a_i\le10^9\)。
先找到整棵树的 \(\text{MAD}\)：如果 \(\text{MAD}\) 出现次数 \(>2\)，根据抽屉原理，不论怎么分答案都是 \(\text{MAD}\)；如果没有 \(\text{MAD}\)，答案都是 0；如果 \(\text{MAD}\) 出现次数 \(=2\)，发现除了 \(\text{MAD}\) 出现的两个位置路径上的边，其他边答案都是 \(\text{MAD}\)，路径上直接暴力便利开桶统计答案即可。时间复杂度 \(\text{O}(n\log n)\)，其中瓶颈为离散化，解决问题只用 \(\text{O}(n)\)。
F1. Survival of the Weakest (easy version)
题意：定义 \(F(a_1,a_2,\ldots a_n)\) 为在 \(a_1,a_2,\ldots a_n\) 中任选一对 \(i,j(i<j)\) 能得到的所有 \(a_i+a_j\) 的前 n-1 个最小值。求 \(\underbrace{F(F(F\ldots F}_{n-1}(a_1,a_2,\ldots,a_n)\ldots))\)。\(n\le3000,a_i\le10^9\)。答案对 \(\text{998244353}\) 取模。
可以联想到 146. 序列 的做法，我们就在 \(\text{O}(n^2\log n)\) 的时间内解决了这个问题。那么取模呢？发现 \(\underbrace{F(F(F\ldots F}_{n-1}(a_1,a_2,\ldots,a_n)\ldots))=\underbrace{F(F(F\ldots F}_{n-1}(0,a_2-a_1,\ldots,a_n-a_1)\ldots))+2^{n-1}a_1\)。
F2. Survival of the Weakest (hard version)
题意：同上，但是 \(n\le2\times10^5\)。
刚刚的做法怎么优化？直觉告诉我们一个数组中较大的一些数是没有用的。更具体地说，我们只需要保留数组中前 \(\text{64}\) 个数，这样就是 \(\text{O}(384n)\) 的（\(384=64\times\log64\)）。那么为什么呢？
如果 \(0,a_1,\ldots,a_n\) 满足 \(a_1+a_2< 0+a_n\)，则 \(a_n\) 可以删除；反之，则 \(F(0,a_1,\ldots a_n)=[0+a_1,0+a_2,\ldots 0+a_n]=[a_1,a_2,\ldots a_n]\) 等价于 \([0,a_2-a_1,\ldots a_n-a_1]\)，\(F(0,a_2-a_1,\ldots a_n-a_1)=[a_2-a_1,a_3-a_1,\ldots a_n']\) 等价于 \([0,a_3-a_2,\ldots a_n'']\)。因为 \(a_n''\le a_n-a_2,a_1+a_2\ge 0+a_n\)，得到 \(a_n''\le\frac{a_n}{2}\)，即两次操作后最后一个数要么消失要么减小至少一半，故只用保留大约 \(2\log{a_n}\approx64\) 个（因为实际操作时我们需要略多保留几个）。
好像可以只保留 \(\text{44}\) 个？没太看懂，把图片放上来吧。
