PROBLEM LINK:
Author: Subash Chandra Manohari
Tester: D Teja Vardhan Reddy
Editorialist: Subash Chandra Manohari
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Segment tree
PROBLEM:
The problem is to find the difference between the IDs of the students having same score in a given range [L,R].
EXPLANATION:
For this interval type of queries, we can think of solving it using segment trees.
We can make a node which can store the minimum and maximum indices of a given mark. If the range represented by a node is completely within the given range, return the node which has the minimum and maximum indices of marks in the range. And if the range represented by a node is partially inside and partially outside the given range, return node of the left child and the right child.
Using this, both Update and Query operation can be done in O(Log n) time and the building of tree will take O(n) time. So the overall time complexity of the solution will be O(n Log n)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here. (Alternate solution)