Editorial for Equalizing Pillars

It is easy to prove that for a given range [L,R][L,R] the best answer comes when we make the pillers height = RL+22th\frac{R-L+2}{2}^{th} element after sorting the range.

So the task is very simple. You have to find the middle element after sorting the [L,R][L,R] elements. If you use merge sort tree it will find the middle element in O(lgN×lgN×lgN)\mathcal{O}(\lg{N}\times \lg{N}\times \lg{N}). To process QQ queries it will take O(Q×lgN×lgN×lgN)\mathcal{O}(Q\times\lg{N}\times \lg{N}\times \lg{N}).

We can reduce the complexity to O(Q×lgN)\mathcal{O}(Q\times\lg{N}) by using Persistent Segment Tree.

Time complexity: O(Q×lgN)\mathcal{O}(Q\times\lg{N})

Memory complexity: O(Q×lgN)\mathcal{O}(Q\times\lg{N})


    48% Solution Ratio

    solaimanopeEarliest, 2M ago

    tanu_RUETFastest, 0.1s

    Nasif_44thLightest, 12 MB

    mh755628Shortest, 1622B