题目要求我们时刻维护一个数列的逆序对个数，n在250000的范围内。虽然可能出现的数字总数只有60000（=50000+10000），但是仍然是一个让人头疼的问题。

对于不需要更改的问题，我们可以用多种方法求出其答案。加入了更改操作之后，我们需要维护相关的内容来更新这个值。

我们回忆块状链表的内容，可以配合做出相应的改变。比如，一开始我们用树状数组（Binary Indexed Trees）求逆序对，那么可以产生相应的块状树状数组。我们通过分块维护来降低维护的费用。

这样一来问题就变得比较简单了。需要说明的是，具体编写程序的时候需要在的基础上加权分块，不然会出现TLE的问题。

• Relative Posts