[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);
}
 

[Codechef] PALINDR - Lucy and Palindromes

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : PALINDR - Lucy and Palindromes
Source            : Codechef
Category          : Data Structure
Algorithm         : Implicit Treap, Lazy Propagation
Verdict           : Accepted 

Operations : 1. Reverse a segment
             2. Lazy Propagation 

 
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define MOD      1000000007
 
static const int MAXN = 1e5 + 5;
 
ll fact[MAXN], ifact[MAXN];
 
struct Node
{
    int cval, priority, sze;
    int cnt[10], rev;
    Node *left, *right;
    Node(int v = 0)
    {
        cval = v;
        priority = rand();
        sze = 1;
        memset(cnt, 0, sizeof cnt);
        cnt[ cval ]++;
        rev = 0;
        left = right = NULL;
    }
};
typedef Node*     pnode;
 
int sz(pnode t)
{
    if (t) return t->sze;
    return 0;
}
 
void updateSize(pnode t)
{
    if (t) t->sze = sz(t->left) + 1 + sz(t->right);
}
 
void push(pnode t)
{
    if (t && t->rev)
    {
        t->rev = 0;
        swap(t->left, t->right);
 
        if (t->left)
            t->left->rev ^= 1;
        if (t->right)
            t->right->rev ^= 1;
    }
}
 
void combine(pnode t)
{
    if (!t)
        return;
    push(t->left);
    push(t->right);
 
    for (int i = 0; i < 10; i++)
        t->cnt[i] = 0;
    t->cnt[ t->cval ]++;
 
    if (t->left)
    {
        for (int i = 0; i < 10; i++)
            t->cnt[i] += t->left->cnt[i];
    }
    if (t->right)
    {
        for (int i = 0; i < 10; i++)
            t->cnt[i] += t->right->cnt[i];
    }
}
 
void Split(pnode t, pnode &l, pnode &r, int pos, int add = 0)
{
    if (!t)
        return void(l = r = NULL);
    push(t);
    int curr = sz(t->left) + add;
    if (curr <= pos)
        Split(t->right, t->right, r, pos, curr+1), l = t;
    else
        Split(t->left, l, t->left, pos, add), r = t;
    updateSize(t);
    combine(t);
}
 
void Merge(pnode &t, pnode l, pnode r)
{
    push(l), push(r);
    if (!l || !r)
        t = l ? l : r;
    else if (l->priority < r->priority)
        Merge(r->left, l, r->left), t = r;
    else
        Merge(l->right, l->right, r), t = l;
    updateSize(t);
    combine(t);
}
 
void update(pnode t, int l, int r)
{
    if (!t) return;
    pnode L, mid, R;
    Split(t, L, mid, l-1);
    Split(mid, t, R, r-l);
    t->rev ^= 1;
    Merge(mid, L, t);
    Merge(t, mid, R);
}
 
ll query(pnode t, int l, int r)
{
    if (!t) return 0;
    int cnt[10];
    pnode L, mid, R;
    Split(t, L, mid, l-1);
    Split(mid, t, R, r-l);
    for (int i = 0; i < 10; i++) cnt[i] = t->cnt[i];
    Merge(mid, L, t);
    Merge(t, mid, R);
    int odd = 0, tot = 0;
    for (int i = 0; i < 10; i++)
    {
        if (cnt[i] & 1) odd++;
        tot += cnt[i];
    }
    if (odd > 1) return 0;
    ll ans = fact[ tot>>1 ];
    for (int i = 0; i < 10; i++)
    {
        ans = (ans * ifact[ cnt[i]>>1 ]) % MOD;
    }
    return ans;
}
 
ll modPow(ll a, ll b, ll m)
{
      if (b == 1) return a % m;
      if (b & 1) return (a % m * modPow(a, b-1, m) % m) % m;
      ll ret = modPow(a, b >> 1, m);
      return (ret % m * ret % m) % m;
}
 
ll modInv(ll a, ll m)
{
      return modPow(a, m-2, m) % m;
}
 
void factorial()
{
    fact[0] = 1;
    ifact[0] = 1;
    for (int i = 1; i < MAXN; i++)
    {
          fact[i] = (i * fact[i-1]) % MOD;
          ifact[i] = modInv(fact[i], MOD) % MOD;
    }
}
 
char s[MAXN];
int n, q;
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    factorial();
    pnode treap = NULL;
    scanf("%d %d", &n, &q);
    scanf("%s", s);
    for (int i = 0; i < n; i++)
    {
        pnode t;
        Merge(t, treap, new Node(s[i] - 'a'));
        treap = t;
    }
    while (q--)
    {
        int type, l, r;
        scanf("%d %d %d", &type, &l, &r);
        l--;  // must
        r--;
        if (type == 1)
        {
            update(treap, l, r);
        }
        else
        {
            printf("%lld\n", query(treap, l, r));
        }
    }
}