用 map
暴力维护每段,如果不小于前一段就把这段直接删了,否则往后暴力删段直到某段小于这一段。每次输出 map
的大小即可。
因为总共至多新建 \(n+m\) 个段,所以均摊复杂度 \(\mathcal O(\log n)\)。
具体细节看代码。
Code:
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 100005;
int T;
int n, m, a[N];
map <int, int> mp;
void upd(int i, int x) {
mp[i] = x;
auto it = mp.find(i);
if (it != mp.begin() && prev(it) -> se <= x) { mp.erase(it); return; }
while (next(it) != mp.end() && next(it) -> se >= x) mp.erase(next(it));
}
void solve() {
scanf("%d%d", &n, &m), mp.clear();
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), upd(i, a[i]);
while (m--) {
int x, y; scanf("%d%d", &x, &y);
a[x] -= y, upd(x, a[x]);
printf("%d ", mp.size());
}
printf("\n");
}
int main() {
scanf("%d", &T);
while (T--) solve();
return 0;
}
标签:map,CF1690G,int,mp,se,define
From: https://www.cnblogs.com/Kobe303/p/16791930.html