T3：
题目大意：
有一个长度为 \(n\) 的数组 \(a\)，有 \(m\) 次询问，每次询问给定一个 \(d\)，表示要求构造出来一个叶子数量为 \(n\) 的深度不超过 \(d\) 的哈夫曼树。
并且要求他叶子权值乘深度和最小。
\(n,m \le 3 \times 10^5\)
解题思路：
这个题目直接做并不好做，考虑他的弱弱弱弱弱化板，就是考虑从这个哈夫曼树上搞点性质。
考虑哈夫曼树的构造过程，每次选择两个和最小的合并，而像这种相加的东西，一个值得注意的地方就在于他较小的那个数的大小会乘 \(2\)。
自然的，我们希望他较大的也乘二，可这并不是事实，但由于每次合并是合并两个最小的，所以对于这次合并较大的数，而过他有儿子的话，就说明这个最小值比他的俩儿子大。
那么对于他的儿子来说，他的爷爷的位置让他的大小乘了个 \(2\)，也就是对于每一个叶子往上跳两个就会翻倍。
所以树高 \(> O(\log{(nV)})\) 答案就不变了。
而且注意到这个哈夫曼树的建造过程是每次合并两个数，这启发我们使用类似归纳法的东西解决这个。
回到原题，考虑判定一个深度数组是否合法，首先从小到大排序之后深度数组不降，其次考虑一个完美二叉树，一个深度为 \(k\) 的点会让他少 \(2^{d - k}\) 个叶子，而如果减到了负数，就一定不合法。
而减不到负数就一定合法。
那么现在相当于求一个数组 \(dep\) 满足 \(\sum_{i = 1}^{n} 2^{-dep_{i}} \le 1\)。
众所周知，\(=\) 一般是不好做的，那么考虑有一个 \(d \times n\) 的棋盘，第 \(i\) 行的权值为 \(2^{-i}\)，第 \(j\) 列的权值为 \(a_{j} \times i\)。
而我们认为这个 \(i\) 并不好做，套路地将它拆到列的前缀里，也就是现在 \(j\) 列的权值为 \(a_{j}\)，而你每次要选一个列的前缀。
这个列的前缀的权值你会发现他对应到之前的条件就变成了 \(1 - 2^{-i}\)，而我们要求 \(\sum_{i = 1}^{n} 2^{-dep_{i}} \le 1\)，对应的变成选和 \(\ge n - 1\)。
而我们要注意这个 \(2^{-i}\) 的特殊的“重量”，这意味着我们的两个深度为 \(i\) 的点的 "重量" 之和“等价”一个深度为 \(i - 1\) 的点。
这正好对应着我们前文说的归纳！
而我们由于要求总和为一个整数，所以对于最下面的一层的点，我们一定要求他出现了偶数次，也就意味着我们 \(2x-1\) 和 \(2x\) 要么同时选，要么同时不选。
我们就可以将他们绑定在一起，变成一个第 \(i - 1\) 层的数。
那么我们就这样递归着去做，由于每个都是一样的。所以可以倒着加。
\(O(n \log nV)\)