CF2007B Index and Maximum Value
思路
如果真的按照题意思路写模拟代码,时间复杂度为O(n*m);
那就换思维:
假设当前最大值是 mx
如果 mx在区间内,它必然会被操作影响。
所有等于 mx的值都一起加/减;
所以新最大值就是 mx+1或 mx−1
如果 mx不在区间内:
当前最大元素完全没动;
而所有其他元素最多变化±1;
不可能超过它;所以最大值不变。
因此我们只需维护一个变量 mx
所以我们只需要一开始找到最大值mx,跟踪mx的变化即可
AC代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;signed main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--){int n, m;cin >> n >> m;vector<ll> a(n);for (int i = 0; i < n; i++){cin >> a[i];}ll mx = *max_element(a.begin(), a.end());while (m--){char op;ll l, r;cin >> op >> l >> r;if (mx >= l && mx <= r){if (op == '+')mx++;elsemx--;}cout << mx << ' ';}cout << '\n';}
}