e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

ADA University - January 13 - Segment Tree

Добуток на відрізку

Це нормально відчувати себе схвильованим та напруженим за день до олімпіади з програмування. Щоб розслабитись, Ви пвшли випити зі своїми друзями у сусідній паб. Для збереження гостроти розуму до наступного дня, Ви вирішили зіграти у наступну гру. Для початку Ваші друзі написали послідовність n цілих чисел x1, x2,..., xn. Потім йде k раундів, у кожному з яких виконується одна з наступних команд:

  • команда зміни, коли необхідно змінити одне значення у послідовності;
  • команда множення, коли за заданими значеннями i та j необхідно визначити, чи є добуток xi * xi+1 * ... * xj-1 * xj доданим, від'ємним чи рівним нулю.

Так як Ви знаходитесь у пабі, то штрафом за неправильну відповідь буде вживання додаткової пінти пива. Ви турбуєтесь, що це може негативно вплинути на Вас при участі у конкурсі на наступний день, і у Вас немає бажання переввряти на коректність теорію піка Баллмера. На щастя, друзі дозволили Вам користуватись ноутбуком. Оскільки Ви більше довіряєте Вашим здібностям програмувати, ніж математиці, то було вирішено написати програму, яка допоможе зіграти у гру.

Вхідні дані

Кожен тест складається з декількох рядків. Перший рядок кожного тесту містить два числа n та k(1n, k105) - кількість елементів у послідовності та число раундів у грі. Другий рядок містить n цілих чисел xi - початкові значення послідовності (-100xi100 для i = 1, 2,..., n). Кожен з наступних k рядків описує команду, яка починається великою буквою 'C' або 'P'. Якщо це буква 'C', то рядок містить команду заміни, за буквою йдуть два числа i та v, які вказують на те, що xi необхідно замінити на v (1in и -100 v100). Якщо це буква 'P', то рядок задає команду множення, за буквою йдуть два числа i та j - необхідно обчислити добуток від xi до xj включно (1 ijn). Кожен тест містить як мінімум одну команду множення.

Вихідні дані

Для кожного тесту вивести один рядок, який містить відповіді на всі команди множення. i-ий символ рядка є результатом i-ої команди множення. Якщо добуток додатний, то вивести символ '+' (плюс); якщо добуток від'ємний, то вивести '-' (мінус); якщо добуток дорівнює нулю, то вивести '0' (нуль).

Ліміт часу 2 секунди
Ліміт використання пам'яті 122.17 MiB
Вхідні дані #1
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
Вихідні дані #1
0+-
+-+-0