KCHIPS - Editorial

PROBLEM LINKS

Practice
Contest

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.