PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
We can answer queries off-line. A very high-level explanation is below.
Let’s have a S ( data structure ) where we store some indices, one for each village. We process villages in increasing order of indices ( as will be explained below ) and in S we just store the Kth most recent index of that village ( if it exists i.e., it occurred more than K times already ) so far, for each of the villages.
We have villages ( indices i ) and queries ( intervals [a,b] ). We take all indices i and all end points of intervals i.e., b’s and sort them and process in increasing order.
When you process an element
-
If its a village index, note it down under the indices of this village. Update S accordingly i.e., remove old Kth recent index and insert new Kth recent index
-
If its a query interval end b, get the corresponding a, and the answer for this query is just the number of integers in S that are greater than equal to a. Store the answer at the query index in ans[] array.
Finally, print ans[] array.
We can use a BIT ( Binary Indexed Tree ) as S. If you are a Java fan, you will love to see the nicely written very abstract solution of the tester.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.