What, I'm stucking with the problem I came up :D.

Блог пользователя i_love_turtles

Автор i_love_turtles, 10 месяцев назад, По-английски

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}$$$?

segment tree, data structures

i_love_turtles
10 месяцев назад
4

Комментарии (4)

Написать комментарий?

pathetique

10 месяцев назад, # |

square root?

→ Ответить

i_love_turtles

10 месяцев назад, # ^ |

+11

Thanks for the hint, but could u explain ur approach further?

→ Ответить

EMBailey

10 месяцев назад, # |

← Rev. 3 →

+19

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.

Example

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:

          (0, 0)
   (0, 0)        (0, 0)
(0, 0) (0, 0) (0, 0) (0, 0)

First, add the smallest element, -2:

          (1,-2)
   (0, 0)        (1,-2)
(0, 0) (0, 0) (1,-2) (0, 0)

There are two 1's, which may be added in either order. Adding the first 1 yields:

          (2,-1)
   (1, 1)        (1,-2)
(1, 1) (0, 0) (1,-2) (0, 0)

Then, adding the second 1 yields:

          (3, 0)
   (1, 1)        (2,-1)
(1, 1) (0, 0) (1,-2) (1, 1)

Finally, add the greatest element, 5:

          (4, 5)
   (2, 6)        (2,-1)
(1, 1) (1, 5) (1,-2) (1, 1)

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.

→ Ответить