binary simulation(light oj).cpp

#include<bits/stdc++.h>
using namespace std;

#define mem(x ,  y) memset(x , y ,sizeof x)
#define M 100005

typedef long long LL ;
LL arr[M +5] , tree[2*M+5 ] , prop[2*M+5];

void build(LL node , LL r1 , LL r2){

    if(r1 ==  r2){
        tree[node] = arr[r1];
    return ;
    }
    LL left , right , mid  ;
    left =  2*node;
    right = 2*node +1 ;
    mid =  (r1 + r2 )/2;

    build(left , r1 , mid  );
    build(right , mid+1  , r2  );
    tree[node] = tree[left ] + tree[right];

}

LL query(LL node ,LL r1 , LL r2 , LL i , LL j ,LL  carry){
    if(r1 > j || i > r2 ) return 0;
    if(r1 >= i &&  r2 <= j ){

        if(carry&1 )
            return    (r2- r1 +1 )- tree[node];
        else
            return tree[node];
    }

    LL left , right , mid ;
    left =  2*node;
    right = left+1;
    mid = (r1 + r2)/2 ;

    LL s1 = query(left , r1 , mid , i , j , carry + prop[node]);
    LL s2 = query(right , mid+1  ,r2 , i , j , carry + prop[node]);

    return  s1+s2 ;

}

void update(LL node ,LL r1 , LL r2 , LL i , LL j ,LL  val ){
    if(r1 > j || i > r2 ) return ;
    if(r1 >= i &&  r2 <= j ){
        prop[node] += val ;
        tree[node] = (r2 - r1 + 1) - tree[node] ;

        //do something
        return ;
    }

    LL left , right , mid  ;
    left =  2*node;
    right = 2*node +1 ;
    mid =  (r1+r2)/2;
    update(left , r1 , mid , i , j , val );
    update(right , mid+1  , r2 ,i , j , val );
    tree[node] = tree[left ] + tree[right];


    return ;

}



int main(){
   //freopen("in.txt " ,"r",stdin);
   // freopen("out.txt " ,"w",stdout);

LL i ,j ,k , tc , cs = 0;
    scanf("%lld",&tc);

    while(tc--){
        getchar();
        printf("Case %d:\n", ++cs);
        mem(prop, 0);

        char str[M+5];

        gets( str);
        k = strlen(str);
        j = 1 ;

        for(i = 0; i < k ;i++)
            if(str[i] == '1')
               arr[j++] = 1;
            else
              arr[j++] = 0;

        build(1 , 1 , k);

        LL qr ;
        scanf("%lld", &qr);
    //  getchar();

        while(qr--){
        char s[10];
        scanf("%s",s);

            if(s[0] == 'I'){
                scanf("%lld%lld",&i , &j );
                update(1 , 1 , k , i ,j ,1 );

            }
            else{
                scanf("%lld",&i );
                j = query( 1, 1, k , i , i , 0);
                printf("%lld\n",j );
            }
        }
    }
    return 0 ;
}