Codeforces 869B Kuriyama Mirai's Stones - Two Arrays

The trick: build two prefix sum arrays.

$1.$ $pref1$ from the original array (for Type 1 queries)

$2.$ $pref2$ from the sorted array (for Type 2 queries)

Sort a copy of the array once at the start. Build prefix sums for both versions. Each query checks its type, then uses the corresponding prefix array. Time: $O(n \log n)$

Time complexity: $O(n \log n)$ for sorting, $O(n)$ for building both prefix arrays, $O(1)$ per query. Total: $O(n \log n + q)$.

Space complexity: $O(n)$ for storing both prefix arrays.