模拟赛，题面

T2

发现不用边分治（

变成启发式合并即可，考虑合并较小较小元素，较大的部分开桶记录即可

考虑将其分为两部分：”被完全包含的mex段与未被完全包含的mex段“

有状态转移方程 $f_{i}=\max\limits_{j\in{i-k+1,i-1}}f_{j-1}+s_imex_{i,j}-s_{j-1}mex_{i,j}$

对于被完全包含的段，可以将 $mex_{i,j}$ 视作斜率，$-s_{j-1}mex_{i,j}+f_{j-1}$ 的最大值视作截距 作李超树，mex变化对应每段的最优决策点不变

对于未被完全包含的段，由于只有一段，因此 $mex$ 固定，同时 $s_i$ 为定值，故 $s_imex$ 为定值，故可以将 $s_{j-1}$ 视作斜率

考虑固定右端点 $r$ ，那么一个合法的 $l$ 需要满足 $\max\limits_{i \in [l,r]}pre_i \le l$
显然是一个后缀，故可以二分

或者说，设 $f_i$ 表示以 $i$ 为右端点的最小左端点，那么为 $f_{r}=\max\limits_{i\in [1,n]} pre_{i}$