Advertisement
Guest User

Mega Inversions

a guest
Jun 14th, 2015
1,151
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define f(i,a,b) for(int i = a; i <= b; i++)
  3.  
  4. typedef long long ll;
  5. using namespace std;
  6.  
  7. const int INF = 1000000000;
  8. const ll INFLL = 100000000000000000ll;
  9. const ll MOD = 1000000007;
  10.  
  11. // ----------------------------------------------------------------------------------------------------------
  12.  
  13. int N;
  14. vector<ll> T1(100005, 0), T2(100005, 0);
  15.  
  16. void update(vector<ll> &t, int x, ll v)
  17. {
  18.     while(x>0)
  19.     {
  20.         t[x] += v;
  21.         x -= x&-x;
  22.     }
  23. }
  24.  
  25. ll query(vector<ll> &t, int x)
  26. {
  27.     ll ret = 0;
  28.     while(x <= N)
  29.     {
  30.         ret += t[x];
  31.         x += x&-x;
  32.     }
  33.     return ret;
  34. }
  35.  
  36. int main()
  37. {
  38.     scanf("%d", &N);
  39.     ll ans = 0;
  40.     f(i,1,N)
  41.     {
  42.         int x;
  43.         scanf("%d", &x);
  44.         update(T1, x, 1);
  45.         int q = query(T1, x+1);
  46.         update(T2, x, q);
  47.         ans += query(T2, x+1);
  48.     }
  49.     cout << ans;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement