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