COJ 2418 - Ivan Operations

//============================================================================
// Name        : Jose Carlos Gonzalez Fernandez
// Author      : Kaga2
// Version     :
// Copyright   : UCI2ndTWF
// Description : Hello World in C++, Ansi-style
//============================================================================


#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>

#include <vector>
#include <limits>
#include <queue>
#include <cstdlib>
#include <string>
#include <map>
#include <math.h>
#include <limits>
#include <time.h>
#include <bitset>
#include <set>
#include <stack>
#include <complex>

using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define uint unsigned int
#define MP make_pair

struct node{
    node *p,*l,*r;

    int car, C[26], vsame, size;
    bool same,rev;

    node(){}
    node(int c){
        car = c;
        C[car] = 1;
        size = 1;
        same = rev = 0;
        l = r = p = NULL;
    }


    void make_same(char x){
        same = 1;
        car = vsame = x;
        memset(C,0,sizeof(C));
        C[car] = size;
    }

    void reverse(){
        rev ^= 1;
        swap(l,r);
    }

    void update(){
        size = 1;
        memset(C,0,sizeof(C));
        C[car] = 1;
        if (l){
            size += l->size;
            for(int i=0;i<26;i++) C[i] += l->C[i];
        }
        if (r) {
            size += r->size;
            for(int i=0;i<26;i++) C[i] += r->C[i];
        }
    }

    void push_down(){
        if (rev){
            rev = 0;
            if (l) l->reverse();
            if (r) r->reverse();
        }
        if (same){
            same = 0;
            if (l) l->make_same(vsame);
            if (r) r->make_same(vsame);
        }
    }
};

void zig(node *p){
    node *q = p->p;
    node *r = q->p;
    if ((q->l = p->r)) q->l->p = q;
    p->r = q, q->p = p;
    if ((p->p = r)){
        if (r->l == q) r->l = p;
        if (r->r == q) r->r = p;
    }
    q->update();
}

void zag(node *p){
    node *q = p->p;
    node *r = q->p;
    if ((q->r = p->l)) q->r->p = q;
    p->l = q, q->p = p;
    if ((p->p = r)){
        if (r->l == q) r->l = p;
        if (r->r == q) r->r = p;
    }
    q->update();
}

node *root;
void splay(node *p, node *fa = NULL){
    while (p->p != fa){
        node *q = p->p;
        if (q->p == fa){
            if (q->l == p)
                zig(p);
            else
                zag(p);
        }
        else{
            node *r = q->p;
            if (r->l == q)
                if (q->l == p)
                    zig(q),zig(p);
                else
                    zag(p),zig(p);
            else
                if (q->l == p)
                    zig(p),zag(p);
                else
                    zag(q),zag(p);
        }
    }
    p->update();
    if (fa == NULL)
        root = p;
    else
        fa->update();
}


char cad[100005];

node *built(int a,int b){
    if (b < a) return NULL;
    int med = (a + b) / 2;
    node *x = new node(cad[med] - 'a');
    if ((x->l = built(a,med-1)))
        x->l->p = x;
    if ((x->r = built(med+1,b)))
        x->r->p = x;
    x->update();
    return x;
}

node *find(int k){
    node *now = root;
    while (true){
        now->push_down();
        if (now->l){
            if (now->l->size >= k){
                now = now->l; continue;}
            k -= now->l->size;
        }
        if (k == 1) break;
        k--;
        now = now->r;
    }
    return now;
}

void REVERSE(int a,int b){
    node *A = find(a);
    node *B = find(b+2);
    splay(A), splay(B,A);
    B->l->reverse();
}

void MAKE_SAME(int a,int b,int c){
    node *A = find(a);
    node *B = find(b+2);
    splay(A), splay(B,A);
    B->l->make_same(c);
    B->update();
    A->update();
}

int QUERY(int a,int b,int c){
    node *A = find(a);
    node *B = find(b+2);
    splay(A), splay(B,A);
    return B->l->C[c];
}


int main(){
    //freopen("/home/jose/Escritorio/mining_sample.in","r",stdin);

    scanf("%s",cad);
    int n = strlen(cad);

    root = new node(0);
    root->l = new node(0);
    root->l->p = root;
    root->l->r = built(0,n-1);
    root->l->r->p = root->l;

    root->l->update();
    root->update();

    char op[23];
    int q;scanf("%d",&q);
    int a,b;
    char c;
    while(q--){
        scanf("%s%d%d",op,&a,&b);
        if (op[0] != 'R') scanf(" %c",&c);

        switch(op[0]){

        case 'S':
            MAKE_SAME(a,b,c - 'a');
            break;

        case 'R':
            REVERSE(a,b);
            break;

        case 'C':
            printf("%d\n",QUERY(a,b,c - 'a'));
            break;
        }
    }

    return 0;
}