Codeforces Round 969 (Div. 2) |
---|
Закончено |
Получив на свой день рождения ещё один массив целых чисел $$$a_1, a_2, \ldots, a_n$$$, Индекс решает выполнить некоторые операции над ним.
Формально, она собирается выполнить $$$m$$$ операций по порядку. Каждая из них относится к одному из двух типов:
Например, если начальный массив $$$a = [7, 1, 3, 4, 3]$$$, после выполнения операции $$$\texttt{+} \space 2 \space 4$$$, массив $$$a = [7, 1, 4, 5, 4]$$$. Затем, после выполнения операции $$$\texttt{-} \space 1 \space 10$$$, массив $$$a = [6, 0, 3, 4, 3]$$$.
Индекс интересует максимальное значение в массиве $$$a$$$. Пожалуйста, помогите ей найти его после каждой из $$$m$$$ операций.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^5$$$) — длина массива и количество операций.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — начальный массив $$$a$$$.
Затем следуют $$$m$$$ строк, каждая строка соответствует операции в следующем формате: $$$\texttt{c l r}$$$ ($$$c \in \{\texttt +, \texttt -\}$$$, $$$l$$$ и $$$r$$$ — целые числа, $$$1 \leq l \leq r \leq 10^9$$$) — описание операции.
Обратите внимание, что элементы $$$a_i$$$ могут не удовлетворять $$$1\le a_i\le 10^9$$$ после некоторых операций, как показано в примере.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$, и сумма $$$m$$$ по всем наборам входных данных не превышает $$$10^5$$$.
Для каждого набора входных данных выведите одну строку, содержащую $$$m$$$ целых чисел, где $$$i$$$-е из них описывает максимальное значение массива после $$$i$$$-й операции.
55 51 2 3 2 1+ 1 3- 2 3+ 1 2+ 2 4- 6 85 51 3 3 4 5+ 1 4+ 2 3- 4 5- 3 3- 2 65 51 1 1 1 1+ 2 3- 4 5+ 1 6- 2 5+ 1 81 11- 1 11 11000000000+ 1000000000 1000000000
4 4 4 5 5 5 5 4 4 3 1 1 2 1 2 0 1000000001
В первом наборе входных данных процесс операций представлен ниже:
Во втором наборе входных данных процесс операций представлен ниже:
Название |
---|