[toph.co] Rio and Inversion

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Rio and Inversion
Source            : toph.co
Category          : Data Structure
Algorithm         : Wavelet Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
   
using namespace std;  
   
#define FI              freopen("in.txt", "r", stdin)  
#define FO              freopen("out.txt", "w", stdout)  
#define FAST            ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)  
   
#define FOR(i, n)       for (int i = 1; i <= n; i++)  
#define ROF(i, n)       for (int i = n; i >= 1; i--)  
#define FORI(i, n)      for (auto i : n)  
#define eb              emplace_back  
#define ll              long long  
#define All(a)          a.begin(), a.end()  
#define lb              lower_bound  
#define mod             1000000007  
   
static const int maxn = 1e5 + 5;  
static const int logn = 18;  
   
struct waveletTree  
{  
      #define vi     vector <int>  
      #define pb     push_back  
   
      int lo, hi;  
      waveletTree *l, *r;  
      vi b;  
   
      waveletTree(int *from , int *to, int x, int y)  
      {  
            lo = x, hi = y;  
            if (from >= to || lo == hi) return;  
            int mid = (lo + hi) >> 1;  
            auto f = [mid](int x)  
            {  
                  return x <= mid;  
            };  
            b.reserve(to-from+1);  
            b.pb(0); // for making 1 indexed  
            for (auto it = from; it != to; it++) b.pb(b.back() + f(*it));  
            auto pivot = stable_partition(from, to, f);  
            l = new waveletTree(from, pivot, lo, mid);  
            r = new waveletTree(pivot, to, mid+1, hi);  
      }  
      inline int LTE(int l, int r, int k)  
      {  
            if (l > r || k < lo) return 0;  
            if (hi <= k) return (r - l + 1);  
            int lb = b[l-1];  
            int rb = b[r];  
            return this->l->LTE(lb+1, rb, k) + this->r->LTE(l-lb, r-rb, k);  
      }  
      inline int EQL(int l, int r, int k)  
      {  
            if (l > r || k < lo || k > hi) return 0;  
            if (lo == hi) return (r - l + 1);  
            int lb = b[l-1];  
            int rb = b[r];  
            int mid = (lo + hi) >> 1;  
            if (k <= mid) return this->l->EQL(lb+1, rb, k);  
            return this->r->EQL(l-lb, r-rb, k);  
      }  
      ~waveletTree()  
      {  
            delete l;  
            delete r;  
      }  
};  
   
int n, q;  
int arr[maxn], temp[maxn];  
ll inversion[maxn], tInversion, suminversion[maxn];  
   
int main()  
{  
      //FI;  
      FAST;  
   
      cin >> n;  
      FOR(i, n)  
      {  
            cin >> arr[i];  
            arr[i]++;  
            temp[i] = arr[i];  
      }  
      waveletTree *T;  
      T = new waveletTree(temp+1, temp+n+1, 1, 100);  
      FOR(i, n)  
      {  
            inversion[i] = T->LTE(i+1, n, arr[i]) - T->EQL(i+1, n, arr[i]);  
            tInversion += inversion[i];  
            suminversion[i] = tInversion;  
      }  
      int q;  
      cin >> q;  
      FOR(_q, q)  
      {  
            int type;  
            cin >> type;  
            if (type == 0) // swap  
            {  
                  int pos1, pos2;  
                  cin >> pos1 >> pos2;  
                  pos1++, pos2++;  
                  if (pos1 > pos2) swap(pos1, pos2);  
                  int val1 = arr[pos1];  
                  int val2 = arr[pos2];  
                  if (val1 == val2)  
                  {  
                        cout << tInversion << endl;  
                        continue;  
                  }  
                  ll bad1 = T->LTE(pos1+1, pos2, val1) - T->EQL(pos1+1, pos2, val1);  
                  ll add1 = (pos2 - pos1) - T->LTE(pos1+1, pos2, val1);  
                  ll bad2 = (pos2-1 - pos1 + 1) - T->LTE(pos1, pos2-1, val2);  
                  ll add2 = T->LTE(pos1, pos2-1, val2) - T->EQL(pos1, pos2-1, val2);  
                  ll ans = tInversion - bad1 + add1 - bad2 + add2;  
                  if (val1 > val2) ans++;  
                  else ans--;  
                  assert(ans >= 0);  
                  cout << ans << endl;  
            }  
            else  
            {  
                  int l, r;  
                  cin >> l >> r;  
                  l++, r++;  
                  if (l > r) swap(l, r);  
                  int sub = suminversion[r] - suminversion[l-1];  
                  FOR(i, 100)  
                  {  
                        int tequal = T->EQL(l, r, i);  
                        if (tequal == 0) continue;  
                        ll large = tequal * (l-1 - T->LTE(1, l-1, i));\  
                        sub += large;  
                  }  
                  ll ans = tInversion - sub;  
                  cout << ans << endl;  
            }  
      }  
}