Задача RSQ (Range Sum Query). Вам дан массив, необходимо отвечать на запросы получения суммы на отрезке и изменение одного элемента массива.
Ссылка на задачу на codeforces.com.
Имя входного файла: rsq.in
Имя выходного файла: rsq.out
Ограничение по памяти: 2 секунды
Ограничение по времени: 256 мегабайт
Формат входного файла
Входной файл в первой строке содержит два числа [latex]n[/latex] [latex]\left(1 \le n \le 10^{5} \right)[/latex] — размер массива и [latex]m[/latex] [latex]\left(1 \le m \le 10^{5} \right)[/latex] — количество запросов. Во второй строке задано начальное состояние массива [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex] [latex]\left( -10^{5} \le a_{i} \le 10^{5} \right)[/latex].
Далее идёт [latex]m[/latex] строк с запросами вида [latex]t[/latex] [latex]x[/latex] [latex]y[/latex] [latex]\left( 0 \le t \le 1 \right)[/latex]. Если [latex]t = 0[/latex], тогда на запрос нужно вывести сумму элементов массива с индексами от [latex]x[/latex] до [latex]y[/latex] (в данном случае [latex]1 \le x \le y \le n[/latex]). Если [latex]t = 1[/latex], тогда надо присвоить элементу массива с индексом [latex]x[/latex] значение [latex]y[/latex] (в этом случае [latex]1 \le x \le n[/latex], [latex]-10^{5} \le y \le 10^{5}[/latex]).
Формат выходного файла
На каждый запрос суммы отрезка выведите одно число в новой строке — запрашиваемая сумма.
Примеры
| rsq.in | rsq.out |
|---|---|
| 5 3 1 2 3 4 5 0 1 5 1 1 -14 0 1 5 |
15 0 |
| 8 2 7 3 -10 4 1 2 5 6 0 2 4 0 5 7 |
-3 8 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <iostream> #include <fstream> using namespace std; int main() { ifstream cin("rsq.in"); ofstream cout("rsq.out"); ios::sync_with_stdio(false); unsigned int n, m, i; long long sum = 0, sum_k; int *a, x, y; bool t; cin >> n >> m; n++; a = new int[n]; for (i = 1; i < n; i++) { cin >> a[i]; sum += a[i]; } const unsigned int ndiv2 = n/2; while (m--) { cin >> t >> x; if (t) { sum -= a[x]; cin >> a[x]; sum += a[x]; } else { cin >> y; y++; if (y - x > ndiv2) { sum_k = sum; for (i = 1; i < x; i++) { sum_k -= a[i]; } for (i = y; i < n; i++) { sum_k -= a[i]; } } else { sum_k = 0; for (; x < y; x++) { sum_k += a[x]; } } cout << sum_k << endl; } } return 0; } |
Решение задачи
Основная идея приведённого выше решения этой задачи заключается в оптимизации обработки запросов суммы построением дерева отрезков.
Сохраним сумму всех элементов массива в переменной
sum. Теперь, если нам дан запрос суммы на отрезке [latex]\left[ x; y \right][/latex], то если [latex]y — x > \frac{n}{2}[/latex] (то есть если данный отрезок содержит больше элементов, чем половина всего отрезка) то считаем сумму элементов на отрезке [latex]\left[ 1; x-1 \right] \cup \left[ y+1; n \right] = \left[ 1; n \right] \setminus \left[ x; y \right][/latex] и отнимаем от суммы всех элементов, иначе (если [latex]y — x \le \frac{n}{2}[/latex], то) просто считаем сумму элементов на отрезке [latex]\left[ x; y \right][/latex]. Если же поступает запрос на замену значения элемента, то вычитаем из
sum старое значение и прибавляем новое.
Таким образом, максимальная сложность запросов суммы (при простом подходе к задаче) уменьшается вдвое.
Хорошо.
Вот только ссылка на задачу http://codeforces.com/group/j3uuUV7Hld/contest/211979/problem/A не будет работать если посетитель не зарегистрирован на codeforces.