下面是代码:
#include<iostream>
using namespace std;
const int MX = 100;
int n,a[MX*2],bit[MX];
void add(int x, int y){
for(;x<=n; x+=-x&x) bit[x]+=y;
}
int query(int x){
int s= 0;
for(;x>0; x-=-x&x) s+=bit[x];
return s;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int ans = 0;
cin >> n; n*=2;
for(int i = 0; i<n; i++){
cin >> a[i];
}
for(int i = n-1; ~i; i--){
ans+=query(a[i]-1);
add(a[i],1);
}
cout << ans;
}
我不明白查询和添加是如何帮助查找数组中的反演次数的。 如果有人能帮我解释一下，那就太好了。 谢了。
首先，我希望您理解add和query如何在bit中工作。 如果不是，就把bit看作是一个黑盒，它存储数组a中元素1，2，。。。，n的前缀和。 例如，a[3]=count(1)+count(2)+count(3)。 add(x，y)按y递增count(x)，而query(x)返回和count(1)+count(2)+...+count(x)，即前缀sum till元素x。
索引i和j处的元素形成反演，如果i； j和arr[i]>； ARR[j]。 但是上面的代码是以另一种方式读取它的； j>； i和arr[j]<; arr[i]（这将保存对query)额外调用。
现在假设数组是{3，4，1，5，2}，并且已经在位中插入了{2，5，1}。 然后查询(1)=1，查询(2)=2，查询(3)=2，查询(4)=2和查询(5)=3（请记住将位看作存储前缀和的黑盒）。 请注意，当索引i指向元素4时，所有已经插入的具有索引j1，j2，。。。，jk的元素都是>； i所以现在我们只需要计算元素的数量； 4，它是我们通过调用查询(3)得到的前缀和直到3。
