### PROBLEM LINK:

**Author:** Rajon Bardhan

### DIFFICULTY:

HARD.

### PREREQUISITES:

Data Structure

### PROBLEM:

Given a number t, which indicates the server holds information of last t seconds.

Next given t integers which means every ith (0 ≤ i ≤ t - 1) second, server records an integer k (type of vehicle).

Next an integer Q (number of queries) is given .

For each query four integers are given t1, t2, type1, type2. Need to find how many vehicles from type1 to type2 are present from time t1 to time t2.

### QUICK EXPLANATION:

The problem is based on MO’s Algorithm. For every query, we need to find out the cumulative summation into a range. Cumulative summation can be find out in O(logN) by using Binary Index Tree or Segment Tree.

Now main point is how to handle queries quickly! For this reason, I use MO’s Algorithm. I suggest to read the following blog to understand MO’s algorithm.

Time Complexity - N√N(logN)

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.