0314
T1
需要最大化满足 $\operatorname{mex}(a[l:r])\ge k$ 的区间个数，又有一个很重要的性质，所有数的个数相差 $1$。
Case1
先从简单的情况考虑，只有 $01$，最大化 $\operatorname{mex} \ge1$ 的区间个数，记 $tot$ 为区间个数总数，它是可以取到 $tot-cnt_0$ 的，方式是 $01$ 隔着放。
Case2
稍稍推广一下，假设每个数的个数都相同，都是 $x$，最大数为 $m-1$，然后需要最大化 $\operatorname{mex} \ge m$ 的区间个数，我们可以以 $0,1,2\cdots m,0,1,2\cdots m,\cdots$ 的方式放，这样确实是最优的，因为每个长度不小于 $m$ 的区间都可以取到，而长度小于 $m$ 的区间一定取不到。
Case3
继续推广，假设每个数个数相差 $1$，最大数为 $m-1$，那么同样可以做到每个长度不小于 $m$ 的区间都满足条件，具体的，将有 $x+1$ 个的数先放一下，然后再放剩下的，每 $m$ 个循环一遍。
Case4
继续推广，现在不一定最大化 $\operatorname{mex}\ge m$ 了，而是 $\operatorname{mex}\ge a$ 了，先考虑所有小于 $a$ 的数，它们的相对顺序必定如 Case3，如果它们的相对顺序不为 Case3 的顺序，那么调整为 Case3 的顺序之后一定不会变劣，因为原有的合法区间调整后同样合法。
接下来的问题变成了在 Case3 的序列中插入若干个数，要最小化 $\operatorname{mex} <a$ 的区间个数，如果一个区间包含了至少 $a$ 个小于 $a$ 的数，那么它就一定合法，于是将小于 $a$ 的数看成 $0$，大于 $a$ 的数看成 $1$，要最小化 $0$ 个数小于 $a$ 的区间数。
我们插入 $1$ 的时候一定是尽可能连续的插入，具体的，任意两段 $1$ 至少间隔 $a$ 个 $0$，否则容易证明将这两段$1$ 移动到一起一定不劣（可能向左也可能向右），因此每一段 $1$ 互不影响，考虑一共有 $k+1$ 段，每一段是 $x_i$，所有不合法的段的贡献可以拆成含 $1$ 和不含 $1$ 的段的贡献。
化简一下：
前面那一坨只和 $a$ 有关，是个常数，考虑后面那一坨。
最终问题
有 $k+1$ 个整数变量 $x_i,i\in[0,k]$，满足 $\sum\limits_{i=0}^kx_i=W$，需要最小化 $-a(x_0+x_k)+\sum\limits_{i=0}^kx_i^2$，其中 $a$ 是一个常数。
首先这个式子在确定了 $x_0+x_k$ 之后就能 $O(1)$ 求最小值，而且是单峰的，可以三分，于是得到一个 $O(m\log n)$ 的做法。
我们需要一种能够线性做法，考虑对 $x_0+x_k$ 梯度下降。
最开始我把学习率设为 $\Large\eta=\frac{1}{e^{\sqrt t}}$，偏移量设为 $\Large\lceil f_\Delta(x)\eta\rceil$，常数差了一点，$f_\Delta$ 表示 $f(x)$ 的差分。
后面发现其实直接让它向梯度反方向移动 $\pm1$ 或者 $\pm2$ 就行。
由于这是个多组询问，而且每次 $W$ 变小，$a$ 变大，$a$ 变大感觉上最优解会右移，$W$ 变小则相反，不同问题的解连续性应该比较强，所以将初始解设定为上一次的最优解。
也许决策点也是单峰的，但我不会证。
复杂度 $O(能过)$ 或者是 $O(m)$。
另一种化简方式
还是考虑上面那个式子，最小化 $-a(x_0+x_k)+\sum\limits_{i=0}^k x_i^2$，考虑向每一个分配 $1$ 的贡献，显然先向 $x_0,x_k$ 分配最好，然后 $x_0,x_k$ 的一次项系数就被改变了，继续贪心分配就行。