### sonthaile2002's blog

By sonthaile2002, history, 9 months ago, ,

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.

• +6

 » 9 months ago, # |   0 Can you give me an example?Lets say a ={1.2.3.4.5}and query: (2,3)What should the answer be?
•  » » 9 months ago, # ^ |   0 9
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 you mean 2+3+4 = 9?(a[1]+a[2]+a[3])
•  » » » » 9 months ago, # ^ |   0 yes
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   -10 (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
•  » » » » » » 9 months ago, # ^ |   0 That surely would work !
•  » » » » » » » 9 months ago, # ^ |   0 Yeah,but its a bit slow the time complexity is O(n*m*log(m)) where n is size of given array and m the size of the array created with the help of the sliding window(m = n-x)so my algorithm is close to O((n^2)*log(n))(a bit faster than that) which is very close to O(n^2)in conclusion my algorithm will work for n < 10^4
 » 9 months ago, # | ← Rev. 3 →   -10 If I will met this problem in contest I will write in this wayLet'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$ — 1Upd2: 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/7to9IHTime complexity $O(n + mlog(n))$
•  » » 9 months ago, # ^ |   0 Your solution is actually incorrect on testcase 2 5 2 1 1 2 
•  » » » 9 months ago, # ^ |   -10 I think now this works https://ideone.com/7to9IH
•  » » » » 9 months ago, # ^ |   0 Nope. 3 3 2 1 1 1 2 Please explain a little more on your solution, so I can understand.
•  » » » » » 9 months ago, # ^ |   0 Isn't the answer 4?
•  » » » » » » 9 months ago, # ^ |   -6 The answer can't be 4 because the only possible values are 3 + 2 = 5 and 2 + 1 = 3.
•  » » » » » » » 9 months ago, # ^ |   0 Oh, my bad, I am solving problem for finding x th largest number and add y consecutive numbers.
 » 9 months ago, # |   0 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)$.
•  » » 9 months ago, # ^ |   0 thank for your help
 » 9 months ago, # |   0 Can you provide link to the problem?
•  » » 9 months ago, # ^ |   0 i can't,sorry