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