Guest User

Untitled

a guest
Jan 21st, 2018
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.65 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int a[1000];
  5. int BIT[1000]={0};
  6.  
  7. // Cumulative Sum Query BIT
  8. void update(int idx ,int val,int n){
  9.  
  10. while (idx <= n){
  11. BIT[idx] += val;
  12. idx += (idx & -idx);
  13. }
  14. }
  15.  
  16. //Sum Query (1,n)
  17. int query(int idx){
  18. int ans = 0;
  19.  
  20. while (idx > 0){
  21. ans += BIT[idx];
  22. idx -= (idx & -idx);
  23. }
  24. return ans;
  25. }
  26.  
  27.  
  28. int main() {
  29.  
  30. int n;
  31. cin>>n;
  32.  
  33. for(int i=1;i<=n;i++){
  34. cin>>a[i];
  35. }
  36.  
  37. // Inversions Count
  38. int ans = 0;
  39. for(int i=n;i>=1;i--){
  40. ans += query(a[i]-1);
  41. update(a[i],1,n);
  42. }
  43. cout<<ans <<endl;
  44.  
  45.  
  46. return 0;
  47. }
Add Comment
Please, Sign In to add comment