GBus Count

Given several cities numbering from 1 to N. There are several buses and each of them covers a consecutive range of cities. Given all these buses and a series of queries, you are asked to return how many buses have covered a city.

This problem is extremely proper for Binary Indexed Tree. Let's say a bus covers cities from a to b inclusively, then we add 1 at position a and minus 1 at position b + 1 in the BIT. Then the query result of position i is how many cities that covers the ith city.

import java.io.*;
import java.util.*;

class BIT {
    private int[] array;
    public BIT(int N) { 
        array = new int[N + 1];
    }
    public void add(int i, int n) {
        while (i > 0 && i < array.length) {
            array[i] += n;
            i += i & -i;
        }
    }
    public int query(int i) {
        int ret = 0;
        while (i > 0 && i < array.length) {
            ret += array[i]; 
            i -= i & -i;
        }
        return ret;
    }
    public void clear() {
        Arrays.fill(array, 0);
    }
}

public class GBusCount {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        BIT bit = new BIT(5000);
        for (int t = 0; t < T; t++) {
            int N = in.nextInt();
            for (int i = 0; i < N; i++) {
                int a = in.nextInt(), b = in.nextInt();
                bit.add(a, 1);
                bit.add(b + 1, -1);
            }
            System.out.printf("Case #%d:", t + 1);
            int Q = in.nextInt();
            for (int i = 0; i < Q; i++) {
                int P = in.nextInt();
                System.out.printf(" %d", bit.query(P));
            }
            System.out.println();
            bit.clear();
        }
    }
}