树状数组实现 查找逆序对

 题意：

输入一个整数n。

接下来输入一行n个整数 。

1<=  <= n ,且每个数字只会出现一次

题解：

按每个数字的大小存入树状数组

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=10000;
int arr[N];
ll a[N];
int n;

ll query(int x){
  ll s=0;
  for(;x;x-=x&(-x)){
    s+=a[x];
  }
  return s;
}

void modify(int p,ll x){
  for(;p<=n;p+=p&(-p)){
    a[p]+=x;
  }
}


int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++){
    scanf("%d",arr+i);
    //让大于arr[i]的元素在数组数组中排在它的前面方便使用前n项和
    arr[i]=n+1-arr[i];
  }
  ll ans=0;
  for(int i=1;i<=n;i++){
    //每一次有多少个大于它的值就会新增多少个逆序对
    ans+=query(arr[i]);
    //然后统计完该数的逆序对后，再将该数放入到树状数组中
    modify(arr[i],1);
  }
  printf("%lld",ans);
  return 0;
}