Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Naim_Hasan's blog

By Naim_Hasan, 4 weeks ago, ,

https://toph.co/arena?contest=mirror-nstu-ice-fest-regional-2020#!/p/beauty-factor

Above problem has almost same pattern as problem described below.

You are given an Array of integer numbers. You have to answer Q query.

For each query you will be given 3 integer- L, R, K; [ 1'based indexing ]

The answer is if you sort the Array elements from index L to R, then what will be the sum of first K element of the Array? { You can't sort the range [L , R] permanently ] }.

Example:

Array = { 8, 7, 6, 5, 4, 3, 2, 1 };

Query 1: 5 8 3 Answer : 21 [ Because K < L, so sorting didn't affect our answer ]

Query 2: 5 8 6 Answer : 27 [ If we perform sort, then first 6 elements will be 8 7 6 5 1, so ans is 27 ]

{ I just learned Merge_Sort_Tree data structure and this problem came to mind. Type_1 query can be answered with prefix_sum algorithm. But how to handle Type_2 query? }

• +6

 » 4 weeks ago, # |   0 Can you provide the link to the problem?
•  » » 4 weeks ago, # ^ |   0 Actually the problem pop up in my mind while learning merge_sort_tree. As each node store a range in sorted order, so i was thinking is it possible to answer for a sorted range without performing sort on real array elements.
 » 4 weeks ago, # | ← Rev. 2 →   0 You could binary search the ending element in the L,R range in a merge sort tree, where each node has sorted elements and prefix sums. Complexity would be log(n) * log(n) * log(max_element) per query.
•  » » 4 weeks ago, # ^ |   0 I figured out that if R <= K, than sorting also doesn't affect the answer just like type_1 query. I got bellowed idea while thinking and walking- Lets say L < K < R means K is somewhere between [L,R]. Now add prefix_sum from 1 to L-1 to the answer. Now we have to find answer for range [L,K]. Here i got confused how to handle this part because after sorting some element of actual array range [L,K] may not be present if we sort range [L,R].
 » 4 weeks ago, # | ← Rev. 2 →   0 Can be done online using persistent segment tree in O(log(n)) for a query or offline using usual segment tree with sorting queries
•  » » 4 weeks ago, # ^ |   0 Can you provide a sample solution for small input?
 » 4 weeks ago, # |   +17 You have no reason to know any algorithms harder than DFS. Really.
•  » » 4 weeks ago, # ^ |   +24 Ouch! True but sometimes people just wanna learn something new instead of focusing purely on increasing their rating I guess?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Didn't get it. Um_nik
•  » » » 4 weeks ago, # ^ |   +3 Your rating is below 1220 for more than a year, which means that you are struggling to solve problems on basic logic skills, ifs and fors. You shouldn't know words "merge sort tree". I don't, for example.
•  » » » » 4 weeks ago, # ^ |   0 Yes, you are right. I still got confused when try to solve A,B from Div_2 and Div_3. Actually my thinking level is still low, so i am trying to focus on problems with fixed data structure and algorithm. [ It was a pleasure to get attention from an LGM ]
•  » » 4 weeks ago, # ^ |   +9 You have no reason to have high rating either ;)
 » 4 weeks ago, # |   0 I think we can solve this by using the solution to SPOJ's KQUERY problem as a subroutine.You can turn each query into 2 parts: What is the kth element of the subarray? What is the sum of elements less than X in the subarray? The first can be answered using the solution for the KQUERY problem. The second can be answered offline using a range tree like fenwick tree or segment tree.
•  » » 4 weeks ago, # ^ |   0 Understood the 2nd part. Each node in Merge_Sort_Tree will keep 2 array. One for storing elements in sorted order and second is for prefix_sum. Now we can perform binary search on 1st array to see if current element is less than X or not. If yes, we can add the range_sum to our answer from 2nd array. [ This problem has the exact same pattern as i explained. Now i have to learn how to handle type_1 query from your comment. Thanks for your time.