1. Идея

Нужно отвечать на запросы вида: какова сумма элементов, стоящих на позициях от l до r после сортировки массива по неубыванию.

Если для каждого запроса заново сортировать или заново суммировать нужный отрезок, это будет слишком долго. Поэтому удобно:

1. один раз отсортировать массив;
2. один раз посчитать массив префиксных сумм;
3. для каждого запроса получать сумму на отрезке за O(1).

Это стандартный приём: сортировка + префиксные суммы.

2. Наблюдения

Наблюдение 1

После сортировки порядок участников уже фиксирован. Значит, все запросы относятся к одному и тому же отсортированному массиву.

Например, если было:

5 1 7 3

то после сортировки получаем:

1 3 5 7

Запрос 2 4 означает сумму элементов 3 + 5 + 7.

Наблюдение 2

Для быстрого нахождения суммы на отрезке нужен массив префиксных сумм.

Пусть pref[i] — сумма первых i элементов отсортированного массива.

Тогда:

• pref[0] = 0
• pref[1] = a[0]
• pref[2] = a[0] + a[1]
• и так далее

Сумма элементов с позиции l по r включительно равна:

pref[r] - pref[l - 1]

Здесь важно, что в условии позиции нумеруются с 1.

Наблюдение 3

Числа могут быть большими, а сумма может не влезать в 32-битный тип. Поэтому:

• в C++ нужно использовать long long;
• в Python это не проблема, там целые числа длинные автоматически.

3. Алгоритм

1. Считать n.
2. Считать массив a из n чисел.
3. Отсортировать a по неубыванию.
4. Построить массив префиксных сумм pref длины n + 1:
   • pref[0] = 0
   • pref[i + 1] = pref[i] + a[i]
5. Считать число запросов q.
6. Для каждого запроса l, r вывести:
   • pref[r] - pref[l - 1]

4. Почему это работает

После сортировки массив a становится именно тем списком результатов, который используется в запросах.

Теперь разберём префиксные суммы.

pref[r] — это сумма первых r элементов отсортированного массива, то есть элементов с позиций от 1 до r.

pref[l - 1] — это сумма элементов с позиций от 1 до l - 1.

Если вычесть вторую сумму из первой, останутся только элементы с позиций от l до r:

pref[r] - pref[l - 1]

Именно это и требуется в запросе.

Значит, каждый ответ вычисляется правильно.

5. Сложность

• Сортировка массива: O(n log n)
• Построение префиксных сумм: O(n)
• Ответ на каждый запрос: O(1)
• Все запросы вместе: O(q)

Итоговая сложность:

O(n log n + q)

Память:

O(n) на хранение массива и префиксных сумм.

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + a[i];
    }

    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << pref[r] - pref[l - 1] << '\n';
    }

    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

a.sort()

pref = [0] * (n + 1)
for i in range(n):
    pref[i + 1] = pref[i] + a[i]

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(pref[r] - pref[l - 1])