Light OJ 1080 – Binary Simulation

Posted on by

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1080

This problem can be solved by using both BIT (Binary Indexed Tree) and Segment tree. Both solution is Here..


/*BIT (Binary Indexed Tree)*/

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             100010
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d%d",&a,&b)
#define sfff(a,b,c)     scanf("%d%d%d",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d:\n",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

int tree[MAX],n;
char str[MAX];

void update2(int indx, int v)
{
    while(indx<=n)
    {
        tree[indx]+=v;
        indx += (indx & (-indx));
    }
}

void update(int i, int j)
{
    update2(i,1);
    update2(j+1,-1);
}

int query(int indx)
{
    int sum=0;
    while(indx)
    {
        sum+=tree[indx];
        indx-=(indx & (-indx));
    }
    return sum;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    sf(t);
    TEST_CASE(t)
    {
        ms(tree,0);
        sc("%s",&str[1]);
        n=strlen(&str[1]);
        char ch;
        int m;
        sf(m);
        PRINT_CASE;
        while(m--)
        {
            getchar();
            sc("%c",&ch);

            if(ch=='I')
            {
                int a,b;
                sff(a,b);
                update(a,b);
            }
            else
            {
                int a;
                sf(a);
                if(query(a)%2==1)
                {
                    if(str[a]=='0') pf("1\n");
                    else pf("0\n");
                }
                else
                    pf("%c\n",str[a]);
            }
        }
    }
    return 0;
}

Another solution using segment tree is here -> 1080 – Binary Simulation(Segment Tree)

2 thoughts on “Light OJ 1080 – Binary Simulation”

    • I think you know that BIT works as a dynamic cumulative sum array. Here If an interval i to j is inverted then we are adding 1 with all the index from i to j. after several invert operation if a query operation come. Then we can check the value of that index. if the value is an even number then we know that even number of invert make the initial value so we print the actual value otherwise we print the inverted value.

      And BIT works as cumulative sum. So if we add 1 to index i then it means we are adding 1 from i to nth index of the cumulative array. but we need to add 1 only i th to j th index. So we are adding a -1 at j+1 th index. So that extra added one from j+1 th index to nth index will vanish.

      Like

Comments are closed.