首页 > 代码库 > Day2:T4用树状数组求逆序对

Day2:T4用树状数组求逆序对

T4: 用树状数组求逆序对

A[I]为前缀和

推导 (A[J]-A[I])/(J-I)>=M

A[j]-A[I]>=M(J-I)

A[J]-M*J>=A[I]-M*I

B[J]>=B[I]

之后就是求逆序对的事情了

然后这里学一下用树状数组的方法

原理是:树状数组是用来求区间和的是吧

就是按权值的区间统计那么可以BIT维护。。。然后扫一遍

也就是计算有多少个逆序对

按权值的区间统计就是记录数的个数

Day2:T4用树状数组求逆序对