Editorial for COCI '20 Contest 6 #5 Index

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

First subtask can be solved by brute force.

The idea for the rest of the solution is to use binary search to determine the $h$ ~h~-index. We need to be able to answer questions of the form "How many numbers on positions $l$ ~l~ through $r$ ~r~ are greater than or equal to $h$ ~h~?" efficiently. The difference between the second and third subtask will be in the data structure we use to answer such queries.

One possible approach is to build a segment tree, where the node corresponding to the interval $[a, b]$ ~[a, b]~ holds the numbers $p_a, p_{a+1}, \dots, p_b$ ~p_a, p_{a+1}, \dots, p_b~ sorted in increasing order. When we query, we use binary search in the appropriate nodes to find how many numbers are greater than $h$ ~h~ in the corresponding interval of the node. Therefore we can answer each question from the problem in $\mathcal O(\log^3 n)$ ~\mathcal O(\log^3 n)~ complexity, which is fast enough for the second subtask.

For all points, there are multiple approaches. One is to use parallel binary search (most solutions on HONI, local version of COCI, were of this type). We will describe a different solution that uses a persistent segment tree. Times will be the prefixes of the array, that is, we will have a "separate" segment tree for each prefix. A node in the tree corresponding to the interval $[a, b]$ ~[a, b]~ will hold the value $cnt_a + cnt_{a+1} + \dots + cnt_b$ ~cnt_a + cnt_{a+1} + \dots + cnt_b~, where $cnt_i$ ~cnt_i~ is the number of elements in the prefix that are equal to $i$ ~i~.

Now we can answer the question "How many numbers on positions $l$ ~l~ through $r$ ~r~ are greater than or equal to $h$ ~h~?" by querying the sum of values in the interval $[h, 200\,000]$ ~[h, 200\,000]~ in moments $r$ ~r~ and $l-1$ ~l-1~, and subtracting them. The complexity per question from the problem is $\mathcal O(\log^2 n)$ ~\mathcal O(\log^2 n)~.

For those who want to know more: there is a solution with $\mathcal O(\log^2 n)$ ~\mathcal O(\log^2 n)~ complexity per question, that uses the same data structure as described for the second subtask. It can be sped up using a technique known as fractional cascading. You can read more about it here.

Comments

0

Snapper_001 commented on Oct. 10, 2024, 12:14 p.m.

This problem is solvable using wavelet Tree in O(log(maxA[I]) * log(n) )

0

muathe14282 commented on March 31, 2023, 3:53 p.m.

This problem is solvable using Parallel Binary Search