codeforces#P2007B. Index and Maximum Value
Index and Maximum Value
Description
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.
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$.
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.
Input
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
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.
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
4 4 4 5 5
5 5 4 4 3
1 1 2 1 2
0
1000000001
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$.