树状数组进行每个长度的的统计逆序对,然后当遇到每一个数的时候进行统计如果取反,会在原本的逆序对基础上进行的变化有哪些。
变化为
1.如果在一个区间上选择第i个点,那么这个数前面的i-1个点肯定都大于它。
2.然后统计这个数后面比他还要小的数(防止重复贡献)
例如 5 4 3 2 1 如果是3这个数变成-3,即:5 4 -3 2 1那么我们的5 4都是逆序对, 但是末尾的2 1并不是逆序对了,这里就需要进行减掉2 1 和原本3组成的逆序对。
注册一个 核OJ_核桃编程 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 核OJ_核桃编程 通用账户