Условие задачи
Это нормально чувствовать себя взволнованным и напряженным за день до олимпиады по программированию. Чтобы расслабиться, вы пошли выпить со своими друзьями в соседний паб. Для сохранения остроты ума до следующего дня, Вы решили сыграть в следующую игру. Для начала Ваши друзья написали последовательность [latex] n [/latex] целых чисел [latex] x_{1}, x_{2},\cdots , x_{n} [/latex]. Потом следует [latex] k [/latex] раундов, на каждом из которых выполняется одна из следующих команд:
- команда изменения, когда необходимо изменить одно значение в последовательности;
- команда умножения, когда по заданным значениям [latex] i [/latex] и [latex] j [/latex] необходимо определить, является ли произведение [latex] x_{i}\cdot x_{i+1} \cdot \; \; \cdots \; \; \cdot x_{j-1} \cdot x_{j} [/latex] положительным, отрицательным или равным нулю.
Так как Вы находитесь в пабе, то штрафом за неправильный ответ будет употребление дополнительной пинты пива. Вы беспокоитесь, что это может негативно повлиять на Вас при участии в конкурсе на следующий день, и у Вас нет желания проверять на корректность теорию пика Баллмера. К счастью, друзья разрешили Вам пользоваться ноутбуком. Поскольку Вы больше доверяете Вашим способностям программировать, нежели математике, то было решено написать программу, которая поможет сыграть в игру.
Входные данные
Каждый тест состоит из нескольких строк. Первая строка каждого теста содержит два числа [latex] n [/latex] и [latex] k [/latex] ([latex] 1\leq n,k\leq 10^{5}[/latex]) — количество элементов в последовательности и число раундов в игре. Вторая строка содержит [latex] n [/latex] целых чисел [latex] x_{i} [/latex] — начальные значения последовательности ([latex] -100\leq x_{i}\leq 100[/latex] для [latex]i=1,2, \cdots ,n[/latex]). Каждая из следующих [latex] k [/latex] строк описывает команду, начинающуюся заглавной буквой [latex] C [/latex] или [latex] C [/latex]. Если это буква [latex] C [/latex], то строка содержит команду замены, за буквой следуют два числа [latex] i [/latex] и [latex] v [/latex], указывающих на то что [latex] x_{i} [/latex] необходимо заменить на [latex] v [/latex] ([latex] 1\leq i\leq n[/latex] и [latex]-100\leq v\leq 100[/latex]). Если это буква [latex] P [/latex], то строка задает команду умножения, за буквой следуют два числа [latex] i [/latex] и [latex] j [/latex] — необходимо вычислить произведение от [latex] x_{i} [/latex] до [latex] x_{i} [/latex] включительно ([latex] 1\leq i\leq j\leq n [/latex]) . Каждый тест содержит как минимум одну команду умножения.
Выходные данные
Для каждого теста вывести одну строку, содержащую ответы на все команды умножения. [latex] i [/latex]-ый символ строки является результатом [latex] i [/latex]-ой команды умножения. Если произведение положительно, то вывести символ [latex] + [/latex] (плюс); если произведение отрицательно, то вывести [latex] — [/latex] (минус); если произведение равно нулю, то вывести [latex] 0 [/latex] (ноль).
Тесты
| Входные данные | Выходные данные |
| 4 6
-2 6 0 -1 C 1 10 P 1 4 C 3 7 P 2 2 C 4 -5 P 1 4 5 9 1 5 -2 4 3 P 1 2 P 1 5 C 4 -5 P 1 5 P 4 5 C 3 0 P 1 5 C 4 -5 C 4 -5 |
0+-
+-+-0 |
| 5 5
10 -2 0 5 1 C 1 0 P 1 4 C 2 7 P 1 1 C 2 0 |
00 |
| 6 4
0 20 0 30 0 -10 P 2 2 P 2 3 P 3 6 P 2 6 4 3 0 -1 -2 0 P 2 3 C 1 9 P 1 2 3 3 5 2 0 C 1 7 C 3 0 C 1 0 6 5 100 10 55 11 0 -33 P 1 4 C 5 6 C 3 72 C 5 -20 P 5 6 |
+000
+-
++ |
Код программы
|
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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <iostream> using namespace std; void sequence(int* tree, int* given, int position, int i, int j) // посторение дерева { if (i == j) tree[position] = given[i] > 0 ? 1 : (given[i] < 0 ? -1 : 0); // заменяем элементы последовательности на "1","-1","0" в соответсвии с условием для команды "P" else if (i!=j) // для остальных элементов воспользуемся следующим алгоритмом { int m = (i + j) / 2; sequence(tree, given, position * 2, i, m); sequence(tree, given, position * 2 + 1, m + 1, j); tree[position] = tree[position * 2] * tree[position * 2 + 1]; // элемент с номером (pos * 2) – левый потомок, а с (pos * 2 + 1) - правый потомок } } void For_C_command(int* tree, int position, int i, int j, int nposition, int v) // функция изменения элемента (для выполнения команлы "С") { if (i == j) tree[position] = v > 0 ? 1 : (v < 0 ? -1 : 0); else if (i!=j) { int m = (i + j) / 2; if (nposition <= m) For_C_command(tree, position * 2, i, m, nposition, v); else For_C_command(tree, position * 2 + 1, m + 1, j, nposition, v); tree[position] = tree[position * 2] * tree[position * 2 + 1]; } } int For_P_command(int* tree, int position, int i, int j, int qi, int qj) // функция для выполнения команды "Р" { if (i == qi && j == qj) return tree[position]; else { int m = (i + j) / 2; if (qj <= m) return For_P_command(tree, position * 2, i, m, qi, qj); else if (qi >= m + 1) return For_P_command(tree, position * 2 + 1, m + 1, j, qi, qj); else return For_P_command(tree, position * 2, i, m, qi, m) * For_P_command(tree, position * 2 + 1, m + 1, j, m + 1, qj); } } int main() { ios::sync_with_stdio(false); // ускоряем чтение int n, k; while (cin >> n >> k) { int given[n]; for (int i = 0; i < n; i++) cin >> given[i]; int tree[n * 4]; sequence(tree, given, 1, 0, n - 1); for (int i = 0; i < k; i++) { char command; int xi, xj; cin >> command >> xi >> xj; if (command == 'P') { int x = For_P_command(tree, 1, 0, n - 1, xi - 1, xj - 1); // применяем функцию для команды "Р" и выполняем сравнения, соответствующие условию задачи if (x < 0) printf("-"); else if (x > 0) printf("+"); else printf("0"); } else For_C_command(tree, 1, 0, n - 1, xi - 1, xj); } printf("\n"); } } |
Решение
Данная задача решается при помощи стандартного алгоритма по теме «Дерево отрезков» (данный алгоритм можно посмотреть на сайте e-maxx). Следовательно, при построении дерева сначала считывается массив, а после выполняется построение дерева (от корня). В том случае, если функция, строящая дерево, вызывалась от листа, все значения элементов массива записываются в дерево как [latex]1[/latex], если элемент больше нуля, если меньше нуля, то записывается как [latex]-1[/latex], а в случае равенства элемента нулю, он записывается [latex]0[/latex] (нулём). В ином случае (если функция вызывалась не от листа), она начинает вызываться рекурсивно от каждого из двух сыновей и перемножает вычесленные значения.
Для выполнения функции изменения элемента ей (функции) передаётся текущая вершина. Затем выполняется вызов из сына, сожержащего элемент с данным номером. Таким образом процесс доходит до листа, которому и присваевается значение. При чём, аналогично построению дерева, элементы записываются как [latex]1[/latex],[latex]-1[/latex] или же [latex]0[/latex].
Для выполнения команды умножения проверяется интервал запроса. В том случае, если они равны интервалам отрезка, возвращается значение элемента (вершины) с соответствующим индексом. Иначе, вызывается рекурсивная функция, которая запускается от правого, если границы запроса лежать в правом отрезке, или от левого сына текущей вершины, если, соответственно, границы исходного запроса лежат в левом отрезке. Рекурсивная функция перемножает полученные результаты в том случае, если она запускает и от левого, и от правого сыновей (т.е. интервал запроса принадлежит пересечению интервалов отрезка).
Далее (в программе) идёт процесс построения дерева и выполнение действий, удовлетворяющих команды, описанные в уловии задачи.
Ссылки
- Рабочий код на Ideone.com
- Засчитанное решение на e-olymp.com
- При ришении данной задачи был использован материал по структурам данных «дерево отрезков» с сайта e-maxx.ru
- Задача взята с сайта e-olymp.com