Index and Maximum Value
Contest: Codeforces Round 969 (Div. 2)
Difficulty rating: 900
Tags: data structures, greedy

After receiving yet another integer array $$$a_1, a_2, \ldots, a_n$$$ at her birthday party, Index decides to perform some operations on it.

Formally, there are $$$m$$$ operations that she is going to perform in order. Each of them belongs to one of the two types:

- $$$\texttt{+ l r}$$$. Given two integers $$$l$$$ and $$$r$$$, for all $$$1 \leq i \leq n$$$ such that $$$l \leq a_i \leq r$$$, set $$$a_i := a_i + 1$$$.
- $$$\texttt{- l r}$$$. Given two integers $$$l$$$ and $$$r$$$, for all $$$1 \leq i \leq n$$$ such that $$$l \leq a_i \leq r$$$, set $$$a_i := a_i - 1$$$.

For example, if the initial array $$$a = [7, 1, 3, 4, 3]$$$, after performing the operation $$$\texttt{+} \space 2 \space 4$$$, the array $$$a = [7, 1, 4, 5, 4]$$$. Then, after performing the operation $$$\texttt{-} \space 1 \space 10$$$, the array $$$a = [6, 0, 3, 4, 3]$$$.

Index is curious about the maximum value in the array $$$a$$$. Please help her find it after each of the $$$m$$$ operations.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^5$$$) — the length of the array and the number of operations.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the initial array $$$a$$$.

Then $$$m$$$ lines follow, each line corresponds to the operation, in the following format: $$$\texttt{c l r}$$$ ($$$c \in \{\texttt +, \texttt -\}$$$, $$$l$$$ and $$$r$$$ are integers, $$$1 \leq l \leq r \leq 10^9$$$) — the description of the operation.

Note that the elements $$$a_i$$$ may not satisfy $$$1\le a_i\le 10^9$$$ after some operations, as it is shown in the example.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output one single line containing $$$m$$$ integers, with the $$$i$$$-th of them describing the maximum value of the array after the $$$i$$$-th operation.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the process of the operations is listed below:

- After the first operation, the array becomes equal $$$[2,3,4,3,2]$$$. The maximum value is $$$4$$$.
- After the second operation, the array becomes equal $$$[1,2,4,2,1]$$$. The maximum value is $$$4$$$.
- After the third operation, the array becomes equal $$$[2,3,4,3,2]$$$. The maximum value is $$$4$$$.
- After the fourth operation, the array becomes equal $$$[3,4,5,4,3]$$$. The maximum value is $$$5$$$.
- After the fifth operation, the array becomes equal $$$[3,4,5,4,3]$$$. The maximum value is $$$5$$$.

In the second test case, the process of the operations is listed below:

- After the first operation, the array becomes equal $$$[2,4,4,5,5]$$$. The maximum value is $$$5$$$.
- After the second operation, the array becomes equal $$$[3,4,4,5,5]$$$. The maximum value is $$$5$$$.
- After the third operation, the array becomes equal $$$[3,3,3,4,4]$$$. The maximum value is $$$4$$$.
- After the fourth operation, the array becomes equal $$$[2,2,2,4,4]$$$. The maximum value is $$$4$$$.
- After the fifth operation, the array becomes equal $$$[1,1,1,3,3]$$$. The maximum value is $$$3$$$.

Example input:
5
5 5
1 2 3 2 1
+ 1 3
- 2 3
+ 1 2
+ 2 4
- 6 8
5 5
1 3 3 4 5
+ 1 4
+ 2 3
- 4 5
- 3 3
- 2 6
5 5
1 1 1 1 1
+ 2 3
- 4 5
+ 1 6
- 2 5
+ 1 8
1 1
1
- 1 1
1 1
1000000000
+ 1000000000 1000000000

Example output:
4 4 4 5 5
5 5 4 4 3
1 1 2 1 2
0
1000000001

Editorial:
We take a maximum value from the initial array. Let's call it $$$a_{pos}$$$.
We can see that $$$a_{pos}$$$ will always be one of the maximum values after any number of operations.
Proof:
Consider the value $$$x$$$ (which should be less than or equal to $$$a_{pos}$$$) before a particular operation.
• If $$$x = a_{pos}$$$, then $$$x = a_{pos}$$$ still holds after the operation.
• Otherwise $$$x < a_{pos}$$$. In the operation, the difference between $$$x$$$ and $$$a_{pos}$$$ decreases by at most $$$1$$$, so $$$x$$$ cannot become strictly greater than $$$a_{pos}$$$.
Then, $$$a_{pos}$$$ remains the maximum value.
So we have reduced the problem to $$$n = 1$$$. Each time a new operation is added, we perform it only on $$$a_{pos}$$$ (and then output $$$a_{pos}$$$).
Time complexity: $$$\mathcal O(n + q)$$$.