CF1690G

标签：map CF1690G int mp se define

用 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