Advertisement
YEZAELP

SPOJ: Boba Inversion

Jan 9th, 2022
558
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. const int N = 5e3 + 10;
  5. vector <int> num;
  6. int ar[N], idx[N], fw[N], ques[N][N];
  7. int n, sz;
  8.  
  9. void Update(int pst){
  10.     for(int i=pst;i<=sz;i+=i&-i)
  11.         fw[i] ++;
  12. }
  13.  
  14. int Sum(int pst, int sum = 0){
  15.     for(int i=pst;i>=1;i-=i&-i)
  16.         sum += fw[i];
  17.     return sum;
  18. }
  19.  
  20. int main(){
  21.  
  22.     scanf("%d", &n);
  23.  
  24.     for(int i=1;i<=n;i++){
  25.         scanf("%d", &ar[i]);
  26.         num.push_back(ar[i]);
  27.     }
  28.  
  29.     sort(num.begin(), num.end());
  30.     num.resize( unique(num.begin(), num.end()) - num.begin());
  31.     sz = num.size();
  32.  
  33.     for(int i=1;i<=n;i++){
  34.         int l = 0, r = sz - 1;
  35.         while(l <= r){
  36.             int mid = (l + r) / 2;
  37.             if(num[mid] == ar[i]){
  38.                 idx[i] = mid + 1;
  39.                 break;
  40.             }
  41.             else if(num[mid] < ar[i])
  42.                 l = mid + 1;
  43.             else
  44.                 r = mid - 1;
  45.         }
  46.     }
  47.  
  48.     for(int i=1;i<=n;i++){
  49.         int ans = 0;
  50.         for(int j=i;j<=n;j++){
  51.             /// [ i , j ]
  52.             ans += Sum(sz) - Sum(idx[j]);
  53.             ques[i][j] = ans;
  54.             Update(idx[j]);
  55.         }
  56.         for(int j=1;j<=sz;j++)
  57.             fw[j] = 0;
  58.     }
  59.  
  60.     int Q;
  61.     scanf("%d", &Q);
  62.  
  63.     for(int q=1;q<=Q;q++){
  64.         int s, e;
  65.         scanf("%d %d", &s, &e);
  66.         printf("%d\n", ques[s][e]);
  67.     }
  68.  
  69.     return 0;
  70. }
Advertisement
RAW Paste Data Copied
Advertisement