Codeforces Round 969 (Div. 2) B题

B. Index and Maximum Value

题目背景

Codeforces Round 969 (Div. 2)

题目描述

给一个数组a

有m次操作，每次操作都是以下二选一
+ l r . 让数组里每一个在$[l,r]$闭区间里面的数字 + 1
- l r . 让数组里每一个在$[l,r]$闭区间里面的数字 - 1

每次操作后输出该数组里的最大值。

一共有$T$组数据。
保证原始数组a里面的数字不会超过$10^9$
$1\le l\le r\le 10^9$

样例 #1

样例输入 #1

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

样例输出 #1

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

做题思路

考虑到最后答案只与最大值相关。

先提出数组里面的最大值。

因为每次操作都是改变$[l,r]$闭区间里面的已有值，所以如果最大值不在该区间内，最大值不变。反之最大值加1或者减1

代码

#include <iostream>
#include <algorithm>
#define int long long
#define For(a,b) for(int i = (a) ; i<= (b) ; i++)
#define IOS {ios::sync_with_stdio(0); cin.tie(0);}
using namespace  std;
const int N = 2e5+10;
int n , m;
int a[N];
void solve(){
    cin >> n >> m;
    int maxa = 0;
    For(1,n){
        cin >> a[i];
        maxa = max(maxa , a[i]);
    }
    char op;int l,r;
    while(m--){
        cin >> op;
        cin >> l >> r;
        if(maxa >= l && maxa <= r){
            if(op == '+')maxa++;
            else maxa--;
        }
        cout << maxa << ' ';
    }
    cout << '\n';
}
signed main(){
    IOS
    int _=1;cin >> _;
    while(_--)solve();
    return 0;
}