首先写出朴素的 DP 方程： $$ dp(i)=\max_{i-k\le j < i}\{ dp(j)+(sum(i)-sum(j))\cdot mex(j,i)\} $$ 首先可以把 $mex(j,i)$ 相同的一段一起处理，只需求出每一段的 $dp(j)-sum(j)\cdot mex(j,i)$ 的最大值。这个值是关于 $mex(j,i)$ 的一次函数，而对所有右端点 $i$，$mex(j,i)$ 相等的段只有 $O(n)$，故我们找到这 $O(n)$ 个段之后，可以用线段树套凸包来求出最大值，时间复杂度 $O(n\log n)$。

每次右端点向右移一位，要找到变化的地方。假设新加的数为 $x$，则原来后缀 $mex$ 为 $x$ 的位置可能会变化。用以 $a_i$ 为下标，位置为值的线段树即可进行查询。这部分时间复杂度为 $O(n\log n)$。

对每一段求出最大值之后，这个最大值是关于 $sum(i)$ 的一次函数，故也可以用凸包来处理。每次修改一段会涉及到删点和加点的操作，但删点无法维护。其实除了最前面的一段，由于每个的 $mex$ 都是递增的，所以不需要删点。而第一段由于受到长度的限制，有可能变小。我们把每段的函数插入到这一段的左端点，每次查询一段后缀即可。时间复杂度 $O(n\log^2n)$。

补充：写的时候发现后半部分可以按时间建线段树，这样就不用动态凸包了，并且时间复杂度为 $O(n\log n)$。