[Toph] Easy Peasy Subset Sum

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Easy Peasy Subset Sum
Source            : Toph
Category          : Data Structures
Algorithm         : Implicit Treap
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll              long long int
 
static const int maxn = 1e5 + 5;
static const ll mod = 1e9 + 7;
 
struct Node
{
      ll val, sum;
      int priority, sze;
      Node *lft, *rgt;
      Node(ll val = 0)
      {
            this->val = val;
            this->sum = val;
            this->priority = rand();
            this->sze = 1;
            this->lft = this->rgt = nullptr;
      }
};
 
typedef Node*             pnode;
 
int sz(pnode t)
{
      return (t == nullptr ? 0 : t->sze);
}
 
void updateSize(pnode t)
{
      if (t) t->sze = sz(t->lft) + 1 + sz(t->rgt);
}
 
void combine(pnode t)
{
      t->sum = t->val;
      if (t->lft) t->sum = (t->sum + t->lft->sum) % mod;
      if (t->rgt) t->sum = (t->sum + t->rgt->sum) % mod;
}
 
void Split(pnode t, pnode &l, pnode &r, int pos, int add = 0)
{
      // 'pos' goes to left subtree
      if (t == nullptr) return void(l = r = nullptr);
      int curr = sz(t->lft) + add;
      if (curr <= pos) Split(t->rgt, t->rgt, r, pos, curr + 1), l = t;
      else Split(t->lft, l, t->lft, pos, add), r = t;
      updateSize(t);
      combine(t);
}
 
void Merge(pnode &t, pnode l, pnode r)
{
      if (l == nullptr or r == nullptr) t = l ? l : r;
      else if (l->priority < r->priority) Merge(r->lft, l, r->lft), t = r;
      else Merge(l->rgt, l->rgt, r), t = l;
      updateSize(t);
      combine(t);
}
 
pnode Insert(pnode t, pnode newnode, int pos)
{
      pnode L, R;
      Split(t, L, R, pos - 1);
      Merge(t, L, newnode);
      Merge(t, t, R);
      return t;
}
 
ll query(pnode t, int pos)
{
      if (t == nullptr || pos <= 0) return 0;
      pnode L, R;
      Split(t, L, R, pos-1);
      ll sum = L->sum;
      Merge(t, L, R);
      return sum;
}
 
ll kth(pnode t, int k)
{
      if (t == nullptr) return -1;
      int curr = sz(t->lft) + 1;
      if (curr == k) return t->val;
      if (curr < k) return kth(t->rgt, k - curr);
      else return kth(t->lft, k);
}
 
int binarySearch(pnode t, ll val)
{
      int lo = 1;
      int hi = sz(t);
      int ans = 0;
      while (lo <= hi)
      {
            int mid = lo + hi >> 1;
            ll k = kth(t, mid);
            if (k <= val) ans = mid, lo = mid + 1;
            else hi = mid - 1;
      }
      return ans;
}
 
void display(pnode t)
{
      if (t == nullptr) return;
      display(t->lft);
      cerr << t->val << ' ';
      display(t->rgt);
}
 
ll power_two[maxn];
 
void power_calc()
{
      power_two[0] = 1;
      for (int i = 1; i < maxn; i++)
      {
            power_two[i] = (1LL * 2 * power_two[i-1]) % mod;
      }
}
 
int main()
{
      #ifndef ONLINE_JUDGE
            freopen("in.txt", "r", stdin);
      #endif // ONLINE_JUDGE
 
      power_calc();
 
      int n;
      cin >> n;
      vector <ll> arr(n);
      for (ll &x : arr) cin >> x;
 
      if (n == 1)
      {
            cout << 0 << '\n';
            exit(0);
      }
 
      pnode treap = nullptr;
      ll cumsum = 0;
      ll sum = 0;
      ll mul = power_two[n-2];
 
      for (int i = n-1; i >= 0; i--)
      {
            ll x = arr[i];
 
            ll small_or_equal = binarySearch(treap, x);
            ll greatter = sz(treap) - small_or_equal;
 
            ll small_or_equal_sum = query(treap, small_or_equal);
            ll greatter_sum = cumsum - small_or_equal_sum;
 
            //cerr << i << " -> " << small_or_equal << " : " << greatter << endl;
            //cerr << small_or_equal_sum << " -- " << greatter_sum << endl;
 
 
            ll p = (small_or_equal * mul % mod * x) % mod;
            ll q = (mul * small_or_equal_sum) % mod;
 
            ll add_small_or_equal = (p - q + mod) % mod;
 
            p = (mul * greatter_sum) % mod;
            q = (mul * x % mod * greatter) % mod;
 
            ll add_greatter = (p - q + mod) % mod;
 
            sum = (sum + add_small_or_equal + add_greatter) % mod;
 
            cumsum = (cumsum + x) % mod;
            x %= mod;
            treap = Insert(treap, new Node(x), small_or_equal);
      }
      cout << sum << '\n';
      //display(treap);
}