[Timus] K-inversions

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : K-inversions 
Source            : Timus
Category          : Data Structure, Policy Based Data Structure
Algorithm         : PBDS
Verdict           : Accepted 



#include <bits/stdc++.h>  
#include <ext/pb_ds/assoc_container.hpp>  
#include <ext/pb_ds/tree_policy.hpp>  
  
using namespace std;  
using namespace __gnu_pbds;  
  
#define int          long long int  
  
static const int maxn = 20000 + 5;  
static const int mod = 1e9;  
  
template <class Node_CItr, class Node_Itr, class Cmp_Fn, class _Alloc>  
struct my_update_policy  
{  
      virtual Node_CItr node_begin() const = 0;  
      virtual Node_CItr node_end() const = 0;  
      typedef int metadata_type;  
  
      int prefix_sum(int x)  // sum of indices <= x  
      {  
            int ans = 0;  
            auto it = node_begin();  
  
            while (it != node_end())  
            {  
                  auto l = it.get_l_child();  
                  auto r = it.get_r_child();  
  
                  if (Cmp_Fn()(x, (*it)->first))  
                  {  
                        it = l;  
                  }  
                  else  
                  {  
                        ans += (*it)->second;  
                        if (l != node_end()) ans += l.get_metadata();  
                        ans %= mod;  
                        it = r;  
                  }  
            }  
            return ans;  
      }  
      void operator()(Node_Itr it, Node_CItr end_it)  
      {  
            auto l = it.get_l_child();  
            auto r = it.get_r_child();  
            int lft = 0;  
            int rgt = 0;  
            if (l != node_end()) lft = l.get_metadata();  
            if (r != node_end()) rgt = r.get_metadata();  
            const_cast <int&> (it.get_metadata()) = (lft + rgt + (*it)->second) % mod;  
      }  
};  
  
template <class T> using ordermap = tree <T, T, less <T>, rb_tree_tag, my_update_policy>;  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int n, K;  
      cin >> n >> K;  
  
      vector <int> arr(n+5), temp(n+5);  
      for (int i = 1; i <= n; i++) cin >> arr[i];  
      ordermap <int> om;  
      for (int i = n; i >= 1; i--)  
      {  
            temp[i] = om.prefix_sum(arr[i]);  
            om.insert({arr[i], 1});  
      }  
      for (int k = 3; k <= K; k++)  
      {  
            om.clear();  
            for (int i = n; i >= 1; i--)  
            {  
                  om.insert({arr[i], temp[i]});  
                  temp[i] = om.prefix_sum(arr[i]-1);  
            }  
      }  
      int sum = 0;  
      for (int i = 1; i <= n; i++) sum = (sum + temp[i]) % mod;  
      cout << sum << '\n';  
}