PROBLEM LINK:Author: Subash Chandra Manohari Tester: D Teja Vardhan Reddy Editorialist: Subash Chandra Manohari DIFFICULTY:EASYMEDIUM 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)
This question is marked "community wiki".
asked 07 Feb, 02:06

Alternate solution without using segment tree. Used sets to store id of students having a particular score. https://www.codechef.com/viewsolution/22915966 answered 07 Feb, 20:50
