Codeforces 869B Kuriyama Mirai's Stones - Implementation

Here's the full solution:

function solve(a, queries)
    n := length of a
    b := copy of a
    sort(b)
    // Build prefix sums for both arrays
    pref1 := array of size n + 1
    pref2 := array of size n + 1
    pref1[0] := 0
    pref2[0] := 0
    for i from 1 to n
        pref1[i] := pref1[i - 1] + a[i]
        pref2[i] := pref2[i - 1] + b[i]
    // Answer queries
    for each (type, l, r) in queries
        if type = 1 then
            print pref1[r] - pref1[l - 1]
        else
            print pref2[r] - pref2[l - 1]

Time: $O(n \log n + q)$ for sorting plus queries. Space: $O(n)$.

The sorted array lets you pick the smallest elements in any range. Prefix sums on both arrays give $O(1)$ range queries.