solution to kattis SuperComputer

super_computer.md

Super Computer

Problem

• Given a binary array, perform two types of queries on it:

  [1] - F x     flip the bit at position x
  [2] - C l r   count the number of set bits in the range [l, r]

Solution Description

• the problem is quite straight forward, those two operations generally describes the a Segment Tree or a Feenwick tree data structures you can read about both of them link . the problem is solvable using both of them .

implementation detail:

• consider having an array initialy having zeros the update operation is just taking the current value in the array index and replacing it by 1 - value to flip it.

public void solve(int testNumber, InputReader in, PrintWriter out) {
    n = in.nextInt();
    m = in.nextInt();
    seg = new int[4 * n];
    SegmentTree tree = new SegmentTree(n) {
      @Override
      public long getNeutral() {
        return 0;
      }
      @Override
      public long operation(long ansLeft, long ansRight) {
        return ansLeft + ansRight;
      }
    };
    for(int i = 0; i < m ; ++i) {
      char op = in.next().charAt(0);
      if(op == 'F') {
        int k = in.nextInt() - 1;
        int cur = (int) tree.query(k , k);
        tree.update(k, k, 1 - cur);
      }else {
        int l = in.nextInt() - 1;
        int r = in.nextInt() - 1;
        out.println(tree.query(l, r));
      }
    }
  }

• another trick to solve the problem not in the most optimal way but it passes for this problem, is using java's BitSet or bitset from cpp to perform the operations, something like this

BitSet b;

int countSetBits(int i, int j) {
    return b.get(i, j+1).cardinality();
}

public void solve(FastReader in, PrintWriter out) {
    int n = in.nextInt(), m = in.nextInt();
    b = new BitSet(n + 1);
    int r , l ;
    String s;
    for (int i = 0; i < m; i++) {
        s = in.next();
        if(s.equals("F")){
            r = in.nextInt();
            b.flip(r);
        }else{
            r = in.nextInt();
            l = in.nextInt();
            out.println(countSetBits(r,l));
        }
    }
}