LightOJ 1080 - Binary Simulation

//Accepted

#include<bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;

const int mod = 1000007;
const int high = 100003;

struct info
{
    LL sum, prop;
};

info tree[3 * high];

void update(int node, int b, int e, int i, int j, int v)
{
    if(i>e or j<b or b > e) return;

    if(b==i and e==j)
    {
        tree[node].sum+= (v * (e-b+1));
        tree[node].prop+=v;
        return;
    }

    int Left = node << 1;
    int Right = Left + 1;
    int mid = (b + e) >> 1;

    if(j<=mid)
    {
        update(Left, b , mid, i , j , v);
    }

    else if(i>mid)
    {
        update(Right, mid+1, e, i, j , v);
    }

    else
    {
        update(Left, b , mid, i , mid, v);
        update(Right, mid+1, e , mid+1, j , v);
    }

    tree[node].sum = tree[Left].sum + tree[Right].sum + (tree[node].prop * (e-b+1));
}

int query(int node, int b , int e, int i, int j, LL carry=0)
{
    if(i>e or j<b or b>e) return 0;

    if(b==i and e==j)
    {
        return tree[node].sum+(carry * (e-b+1));
    }

    int Left = node << 1;
    int Right = Left + 1;
    int mid = (b + e) >> 1;

    if(j<=mid)
    {
        return query(Left, b , mid, i , j , carry+tree[node].prop);
    }

    else if(i>mid)
    {
        return query(Right, mid+1, e , i , j , carry+tree[node].prop);
    }

    else
    {
        LL p1 = query(Left, b , mid, i ,mid, carry+tree[node].prop);
        LL p2 = query(Right, mid+1, e , mid+1, j, carry+tree[node].prop);

         return p1+p2;
    }
}

int main()
{
    //fast;
    int t , tc=0 , n , q , i , j, ans;
    char ch;
    char s[high];
    sf("%d", &t);
    while(t--)
    {
        memset(tree, 0, sizeof(tree));

        getchar();
        gets(s);
        n = strlen(s);

        for(i=0; i<n; i++)
        {
            update(1, 0, n-1, i , i, s[i]-48);
        }

        sf("%d", &q);

        pf("Case %d:\n", ++tc);

        while(q--)
        {
            sf(" %c", &ch);

            if(ch == 'Q')
            {
                sf("%d", &i);

                ans = query(1, 0, n-1, i-1 , i-1 , 0) & 1 ? 1 : 0;

                pf("%d\n", ans);
            }

            else
            {
                sf("%d %d", &i , &j);
                update(1, 0, n-1, i-1 , j-1, 1);
            }
        }
    }

    return 0;
}