一个月没做题了，手感全无，哎。

拆分成：代价为 $x_i$ 的一个糖果，与代价为 $x_i+y_i$ 的无限个糖果。贪心选择 $x$ 最小的若干糖果与 $x_i+y_i$ 最小的糖果即可。

考虑什么时候不优。也就是，你有一个大小为 $2$ 的放不进去跳过（但实际上把某个大小为 $1$ 的扔掉你就能放进去了）。

考虑枚举这个 $2$ 与这个 $1$，然后发现贡献是一堆组合数和 $2$ 的幂，容易做到 $O(n^2)$。

【不确定算法正确性，但是他通过了所有大样例】

类似费用延迟计算的想法，如果子树的 mex 为 $v$，那么其中所有 $>v$ 的数我们不需要知道具体值，我们称之为自由量。

然后调整法弄一下发现，每个点它的 mex，主要取决于它的某个儿子——也就是说，最优情况下每个点的 mex 将会是它某个儿子的 mex 加上一些东西。这样把每个点和他的关键儿子配对，得到了一个树剖分。

树剖分的好处是，虚边是无用的，我们可以直接断掉。然后每个点它会在其某个祖先处从无用点变成有用点，它的贡献为——将某条实链的一个前缀的 mex 全部加 1。

我们可以快乐的树上 DP 了，复杂度 $O(nm \log n)$。

首先，如果 $r \le 2l$，存在一个显然的做法：$i$ 到左右某个端点的距离一定 $\le l$，那么我们对每个 $j$ 计算以他为左端点的符合要求的子段的最大权值 $m_j$，让 $res_i$ 对 $\max_{i-l+1 \le j \le i} m_j$ 取 $\max$ 即可，然后翻转序列再做一次。

因此我们可以把 $[l,r]$ 拆成 $[l,2l]$、$[2l+1,4l+3]$、$\cdots$，这样在 $O(nq \log n)$ 的复杂度内解决了本题。

进一步的，预处理 $l=2^k,r=2^{k+1}$ 的答案，就可以做到 $O(nq)$。

过不去，妈的。