b120. 最大值 - 旦旦解題農場

內容

After receiving yet another integer array $a_{1}$ , $a_{2}$ ,…, $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:

+ l r, Given two integers l and r, for all 1≤i≤n such that l≤ $a_{i}$ ≤r, set $a_{i}$ := $a_{i}$ +1.
- l r. Given two integers l and r, for all 1≤i≤n such that $a_{i}$ , set $a_{i}$ := $a_{i}$ −1.

For example, if the initial array a=[7,1,3,4,3], after performing the operation + 2 4, the array a=[7,1,4,5,4]. Then, after performing the operation - 1 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≤t≤2⋅ $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≤n≤ $10^{5}$ , 1≤m≤ $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}$ ,…, $a_{n}$ (1≤ $a_{i}$ ≤ $10^{9}$ ) — the initial array a. Then m lines follow, each line corresponds to the operation, in the following format: c l r (c∈{+,-}, l and r are integers, 1≤l≤r≤ $10^{9}$ ) — the description of the operation. Note that the elements $a_{i}$ may not satisfy 1≤ $a_{i}$ ≤ $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.

範例輸入

範例輸出

4 4 4 5 5

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (100%): 1.0s , <1K

提示：

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.

標籤:

13th初階班上學期第一次期中考

出處:

Codeforces [管理者：

perry1202 (13th 初階助教)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」