# AUTCN-Editorial

Contest

Author: Rajon Bardhan

HARD.

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.

There exists a simple O(nlogn + mlogn) solution using persistant segment tree.
https://www.codechef.com/viewsolution/11164591