这题题解都用的是树状数组，但是我觉得权值线段树更好写。但是写出来样例 #2 始终 WA 掉。

求指出 bug 并轻喷。

大体思路还是一样的，离散化后维护比 $a_i$ 小的数的权值和及其数量。再注意 $k$ 的限制。

代码放二楼。