Hi guys. Recently, i have been thinking about a new problem but I can't even come up the solution myself LOL. Any ideas to solve this? (Sorry for my poor English btw)
Statement:
Given an array a consists of N integers (-1e6 <= a[i] <= 1e6). You have to answer Q queries, each of them you are given:
t L R k
- If t = 1, return to sum of k largest numbers in range [L, R]
- If t = 2, return to sum of k smallest numbers in range [L, R]
Given that both N and Q are smaller than $$$10 ^ {5}$$$. How do we suppose to solve this problem? Is it solvable if the constraints of N, Q up to 2.$$$10 ^ {5}$$$?
square root?
Thanks for the hint, but could u explain ur approach further?
I'll show how to handle queries of type 2 in $$$\mathcal{O}\left(n \log n + q \log^2 n\right)$$$ time and $$$\mathcal{O}\left(n \log n\right)$$$ auxiliary memory. Queries of type 1 can be handled almost identically.
The main idea is to start with all elements of the array "deactivated" and "activate" each element in increasing order, breaking ties arbitrarily. We'll maintain a persistent segment tree where each node stores the number of activated elements in its segment and the sum of those elements.
Suppose we have the array
[1, 5, -2, 1]. The pair(n, s)represents a segment with n activated elements that sum to s. Initially, our segment tree looks like this:First, add the smallest element, -2:
There are two 1's, which may be added in either order. Adding the first 1 yields:
Then, adding the second 1 yields:
Finally, add the greatest element, 5:
So far, our time complexity is $$$\mathcal{O}\left(n \log n\right)$$$ for sorting the array's indices and $$$\mathcal{O}\left(\log n\right)$$$ for each of the $$$n$$$ activated elements, for a total of $$$\mathcal{O}\left(n \log n\right)$$$ time. Also, since the segment tree is persistent, each activation copies all of the $$$\mathcal{O}\left(\log n\right)$$$ nodes on the path to some leaf, for a total of $$$\mathcal{O}\left(n \log n\right)$$$ auxiliary space.
For a query of the form
2 L R k, we need to find the sum of the k smallest elements in [L, R]. Note that as elements were activated, the number of activated elements in each subarray was non-decreasing. Therefore, we can binary search for the time t at which the subarray [L, R] has k activated elements. This takes $$$\mathcal{O}\left(\log n\right)$$$ queries, each of which takes $$$\mathcal{O}\left(\log n\right)$$$ time. We know that at time t, the activated elements in [L, R] are exactly the k smallest elements in that interval: by the definition of t, exactly k elements are activated, and they were activated in increasing order. Finally, query the sum of those elements in [L, R] at that time t in $$$\mathcal{O}\left(\log n\right)$$$ time. This answers each query in $$$\mathcal{O}\left(\log^2 n\right)$$$ time.To handle queries of type 1, do the same precomputation, but activate the elements in decreasing order instead.
I got it!! Thank you for your dedication and that's detailed explanation :)