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 };

Lets answer 2 query.

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

Can you provide the link to the problem?

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.

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.

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].

Can be done online using persistent segment tree in O(log(n)) for a query or offline using usual segment tree with sorting queries

Can you provide a sample solution for small input?

You have no reason to know any algorithms harder than DFS. Really.

Ouch! True but sometimes people just wanna learn something new instead of focusing purely on increasing their rating I guess?

Didn't get it. Um_nik

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.

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 ]

You have no reason to have high rating either ;)

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:

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.

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.