YEZAELP

o15_oct_inversion

Jan 9th, 2022 (edited)
139
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const int N = 1e5;
  6. int fw[N + 10], ar[N + 10];
  7. vector <int> num;
  8. int n, sz;
  9.  
  10. void Update(int pst){
  11.     for(int i=pst;i<=sz;i+=i&-i)
  12.         fw[i] ++;
  13. }
  14.  
  15. int Sum(int pst, int sum = 0){
  16.     for(int i=pst;i>=1;i-=i&-i)
  17.         sum += fw[i];
  18.     return sum;
  19. }
  20.  
  21. int main(){
  22.  
  23.     scanf("%d", &n);
  24.  
  25.     for(int i=1;i<=n;i++){
  26.         scanf("%d", &ar[i]);
  27.         num.push_back(ar[i]);
  28.     }
  29.  
  30.     sort(num.begin(), num.end());
  31.     num.resize( unique(num.begin(), num.end()) - num.begin() );
  32.     sz = num.size();
  33.  
  34.     lli ans = 0;
  35.     for(int i=1;i<=n;i++){
  36.         int idx;
  37.         {
  38.             int l = 0, r = sz - 1;
  39.             while(l <= r){
  40.                 int mid = (l + r) / 2;
  41.                 if(num[mid] == ar[i]){
  42.                     idx = mid + 1;
  43.                     break;
  44.                 }
  45.                 else if(num[mid] < ar[i]) l = mid + 1;
  46.                 else r = mid - 1;
  47.             }
  48.         }
  49.         ans += Sum(sz) - Sum(idx);
  50.         Update(idx);
  51.     }
  52.  
  53.     printf("%lld", ans);
  54.  
  55.     return 0;
  56. }
RAW Paste Data Copied