e-olymp 4082. Произведение на отрезке

Условие задачи

Это нормально чувствовать себя взволнованным и напряженным за день до олимпиады по программированию. Чтобы расслабиться, вы пошли выпить со своими друзьями в соседний паб. Для сохранения остроты ума до следующего дня, Вы решили сыграть в следующую игру. Для начала Ваши друзья написали последовательность [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

+-

 

++

Код программы

Решение

Данная задача решается при помощи стандартного алгоритма по теме «Дерево отрезков» (данный алгоритм можно посмотреть на сайте 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

e-olymp 2941. Дима и массив

Задача взята с сайта e-olymp.com

Условие задачи

Мама подарила мальчику Диме массив длины [latex]n[/latex]. Массив этот не простой, а особенный. Дима может выбрать два числа [latex]i[/latex] и [latex]d[/latex] ([latex]1\leq i\leq n[/latex], [latex]-1000\leq d\leq 1000[/latex]), и элемент с индексом [latex]i[/latex] магически становится равным [latex]d[/latex]. Дима играет со своим массивом, а мама время от времени задает ему вопросы — какова сумма всех чисел в массиве с индексами от [latex]f[/latex] до [latex]t[/latex]? Дима легко справился с этими вопросами, сможете ли Вы?

Входные данные

В первой строке находятся два целых числа [latex]n[/latex] и [latex]q[/latex] [latex]1\leq n\leq 5\cdot 10^{5},~1\leq q\leq 10^{5}[/latex] — количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано [latex]n[/latex] чисел [latex]a_{1},a_{2},\ldots,a_{n}[/latex] [latex]\left ( -1000\leq a_{i}\leq 1000 \right )[/latex] — начальное состояние массива. В следующих [latex]q[/latex] строках заданы операции и запросы. Первый символ в строке может быть [latex]=[/latex] или [latex]?[/latex]. Если строка начинается с [latex]=[/latex], то это операция присваивания. Далее следуют [latex]i[/latex] и [latex]d[/latex], ограничения на которые описаны в условии. Если строка начинается с [latex]?[/latex], то это запрос. Далее следуют числа [latex]f[/latex] и [latex]t[/latex] [latex]\left (1\leq f,~t\leq n \right )[/latex].

Выходные данные

Для каждого запроса выведите сумму чисел в массиве с индексами от [latex]f[/latex] до [latex]t[/latex], по одному результату в строке.

Тесты

Входные данные Выходные данные
3 3
1 2 3
? 1 3
= 3 2
? 1 3
6
5
5 3
1 2 3 4 5
? 1 5
= 1 7
? 1 3
15
12
5 6
1 2 3 4 5
? 1 5
= 1 0
? 1 5
= 2 7
? 1 5
? 1 3
15
14
19
10

Код программы

ideone.com

Засчитанное решение на e-olymp.com.

Решение

Для решения данной задачи необходимо воспользоваться структурой данных «дерево отрезков».

Для построения дерева считываем исходный массив, затем запускаем функцию построения от корня дерева. Если длина массива не равна единице или функция была запущена не от листа, то она вызывается рекурсивно от каждого из двух сыновей и суммирует вычисленные значения. Если функция построения была вызвана от листа, то значения элементов массива записываются в дерево.

Для операции присваивания передаем рекурсивной функции  текущую вершину дерева и она выполняет вызов от одного из своих сыновей, который содержит элемент с данным индексом. Пересчитывает суммы и доходит до листа, которому присваивается новое значение.

Для выполнения запроса суммы также используется рекурсивная функция. Она запускается либо от правого, либо от левого сына текущей вершины, если границы исходного запроса лежат в одном из их отрезков. Либо запускается от обоих сыновей, если границы исходного запроса принадлежат пересечению их отрезков, суммируя результаты двух запросов. Таким образом функция доходит до отрезка, границы которого совпадают с текущим запросом или до листа и возвращает их значение.

Для решения данной задачи были использованы материалы сайта e-maxx.ru.