UVa 11402 - Ahoy, Pirates

//darkstallion's template

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<map>
#include<list>
#include<set>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
#include<string>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define popb pop_back
#define del erase
#define sz size
#define ins insert
#define FOR(a,b,c) for(int a = b; a < c; a++)
#define FORS(a,b,c) for(int a = b; a <= c; a++)
#define FORN(a,b) for(int a = 0; a < b; a++)
#define FORD(a,b,c) for (int a = b; a >= c; a--)
#define RES(a,b) memset(a,b,sizeof(a))
#define LL long long
#define PII pair<int,int>
#define PLL pair<long long,long long>
#define PDD pair<double,double>
#define PCC pair<char,char>
#define PSS pair<string,string>
#define PI 3.1415926535897932384626433832795
#define eps 1e-9
using namespace std;

string s;
int stree[1<<21], len[1<<21];
char type[1<<21];

void st_build(int idx, int l, int r)
{
    if (l == r)
        stree[idx] = (int)s[l]-'0';
    else
    {
        st_build(idx*2+1, l, (l+r)/2);
        st_build(idx*2+2, (l+r)/2+1, r);
        stree[idx] = stree[idx*2+1] + stree[idx*2+2];
    }
    type[idx] = -1;
    len[idx] = r-l+1;
}

void setType(int idx, char c)
{
    if (c == 'I')
    {
        if (type[idx] == 'F')
            type[idx] = 'E';
        else if (type[idx] == 'E')
            type[idx] = 'F';
        else if (type[idx] == 'I')
            type[idx] = -1;
        else
            type[idx] = 'I';
    }
    else
        type[idx] = c;
}

void st_change(int idx)
{
    if (type[idx] == 'F')
        stree[idx] = len[idx];
    else if (type[idx] == 'E')
        stree[idx] = 0;
    else if (type[idx] == 'I')
        stree[idx] = len[idx]-stree[idx];
    if ((type[idx] != -1) && (len[idx] > 1))
    {
        setType(idx*2+1,type[idx]);
        setType(idx*2+2,type[idx]);
        type[idx] = -1;
    }
}

void st_update(int idx, int l, int r, int i, int j, char c)
{
    if ((l >= i) && (r <= j))
        setType(idx,c);
    st_change(idx);
    if ((l >= i) && (r <= j))
        return;
    if ((r < i) || (j < l))
        return;
    st_update(idx*2+1, l, (l+r)/2, i, j, c);
    st_update(idx*2+2, (l+r)/2+1, r, i, j, c);
    stree[idx] = stree[idx*2+1] + stree[idx*2+2];
}

int st_query(int idx, int l, int r, int i, int j)
{
    st_change(idx);
    if ((r < i) || (j < l))
        return 0;
    if ((l >= i) && (r <= j))
        return stree[idx];
    int p1 = st_query(idx*2+1, l, (l+r)/2, i, j);
    int p2 = st_query(idx*2+2, (l+r)/2+1, r, i, j);
    stree[idx] = stree[idx*2+1] + stree[idx*2+2];
    return p1+p2;
}

int main()
{
    int t;
    scanf("%d",&t);
    FORN(i,t)
    {
        s = "";
        int m;
        scanf("%d",&m);
        FORN(j,m)
        {
            int x;
            string st;
            scanf("%d",&x);
            cin >> st;
            FORN(k,x)
                s += st;
        }
        st_build(0,0,s.sz()-1);
        printf("Case %d:\n",i+1);
        int q,qno = 0;
        scanf("%d",&q);
        FORN(j,q)
        {
            char c;
            int x,y;
            getchar();
            scanf("%c %d %d",&c,&x,&y);
            if (c == 'S')
            {
                qno++;
                printf("Q%d: %d\n",qno,st_query(0,0,s.sz()-1,x,y));
            }
            else
                st_update(0,0,s.sz()-1,x,y,c);
        }
    }
}