rt，我觉得这个题显然是可以做 $O(n\log n)$ 之类的复杂度的。发这个主要是为了征求比较简洁的做法。

下面主要是我目前的一些思考。

我觉得比较靠谱的一个做法是，原来的做法等价于每次拎出一个长度为 $k$ 的有序序列和原来的长度为 $n$ 的有序序列归并后取前 $n$ 大，然后如果要更新的话应该是用长为 $k$ 的序列的一段前缀去替换原序列的一段后缀，然后这个长度满足单调性因此可以直接维护一棵平衡树然后在上面二分？

感觉是对的，如果有问题的话请指出，感激不尽。

由于每个元素被换掉后不会加回来因此复杂度应该是有保证的。

但是由 这个帖子 我觉得应该存在更简单的维护方法，不过我试了试不太写的明白。