rt，主席树板子一个，甚至我用了莫队+二分+树状数组都能过，$O(n\ \sqrt{n}\ log\ log\ n)$ 都能过，数据惊人。

主席树做法