[关闭]
@zzzc18 2017-12-16T10:18:18.000000Z 字数 689 阅读 1597

BIT树状数组求逆序对

BIT 模板库


树状数组求逆序对;
直接按权值排序离散,将位置插入树状数组,该位置的前缀和就是权值比其小而比它大的数的个数

  1. #include<cstdio>
  2. #include<algorithm>
  3. #define MAXN 50000
  4. #define lowbit(x) ((x)&(-x))
  5. int n;
  6. struct data{
  7. int val,id;
  8. }num[MAXN];
  9. bool cmp(const data &x,const data &y){
  10. return x.val<y.val;
  11. }
  12. class Binary_Tree{
  13. private:
  14. int tree[MAXN];
  15. public:
  16. void insert(int pos,int val){
  17. int i;
  18. for(i=pos;i<=n;i+=lowbit(i))
  19. tree[i]+=val;
  20. }
  21. int getnum(int pos){
  22. int i;int ans=0;
  23. for(i=pos;i;i-=lowbit(i))
  24. ans+=tree[i];
  25. return ans;
  26. }
  27. }BIT;
  28. void solve(){
  29. int i;int sum=0;
  30. for(i=1;i<=n;i++){
  31. BIT.insert(num[i].id,1);
  32. sum+=i-BIT.getnum(num[i].id);
  33. }
  34. printf("%d\n",sum);
  35. }
  36. int main(){
  37. scanf("%d",&n);
  38. int i;
  39. for(i=1;i<=n;i++){
  40. scanf("%d",&num[i].val);
  41. num[i].id=i;
  42. }
  43. std::sort(num+1,num+n+1,cmp);
  44. solve();
  45. return 0;
  46. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注