You are given an array a of n integers (n <= 1e5, a [i] <= 1e5) and m (m <= 1e4) the query has the form (x, y) meaning that finding the xth largest value is made by y consecutive numbers in array a. please help me solve this problem? Thanks. And sorry because of my poor English.
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
Can you give me an example?
Lets say a ={1.2.3.4.5}
and query: (2,3)
What should the answer be?
9
you mean 2+3+4 = 9?(a[1]+a[2]+a[3])
yes
(i'm not very experienced programmer)
a simple idea is that you create a sliding window of length y(if you don't know what is sliding window click here) and store the values from the sliding window in a vector/array(i will call it sums) then sort that array and take the sums[x-1](if you are using starting index 0) or sums[x] if you are using starting index 1)
if you need code tell me
That surely would work !
If I will met this problem in contest I will write in this way
Let's create some array $$$b$$$ where we save pair {$$$ a[i], i $$$} to sort them and save every position of element which largest one in array, and after that we can create simple segment sum tree, and answer for every query $$$x$$$ is position of element and $$$y$$$ is position of element + $$$y$$$ — 1
Upd2: My approach is wrong, I am solving problem for finding x th largest number and add y consecutive numbers
Upd: There is the approach https://ideone.com/7to9IH
Time complexity $$$O(n + mlog(n))$$$
Your solution is actually incorrect on testcase
I think now this works https://ideone.com/7to9IH
Nope.
Please explain a little more on your solution, so I can understand.
Isn't the answer 4?
The answer can't be 4 because the only possible values are 3 + 2 = 5 and 2 + 1 = 3.
Oh, my bad, I am solving problem for finding x th largest number and add y consecutive numbers.
If TL is high enough there is a $$$O(n \cdot m)$$$ solution. For each query just calculate the needed sums and use k-th statistics which works in $$$O(n)$$$.
thank for your help
Can you provide link to the problem?
i can't,sorry