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.
http://blog.anudeep2011.com/mos-algorithm/
Time Complexity - N√N(logN)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.