# 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();