转化条件+线段树
由于值域不大，并且删数操作跟序列顺序无关，只和每个数的出现次数有关，考虑在值域上分析删数操作。发现对于每一个值 \(i\) 可以抽象为覆盖了 \([i-buc_{i}+1,i]\) 的区间。要使数列删空，就要让 \([1,n]\) 被填满。这样我们就会发现答案就是 \([1,n]\) 中未被覆盖的值的数量。
证明：
- 首先对于每个空，我们至少要移动一次使得空被填满。所以空缺的数量是答案下界。
- 假如空的数量为 \(k\)，那么一定有 \(k\) 个被多次覆盖或不在 \([1,n]\) 范围内的值，使得将这些位置的值修改为这些空的值后数列能够被删空。
接下来考虑修改操作，
对于单点修改，实际上就是删去原来的覆盖，添加新的覆盖。
对于数列整体加，可以看成覆盖位置的平移，等价于判断范围（指 \([1,n]\)）的相反移动。所以维护判断范围的起始位置 \(st\)，那么只需要查询 \([st+1,st+n]\) 未被覆盖的值的数量即可。
于是考虑用线段树维护这些操作。维护区间最小值 \(mn\)、最小值数量 \(mncnt\)、答案 \(ans\) 以及懒标记。
关于合并，其他显然。当 \(mn=0\) 时，\(mncnt\) 即为 \(ans\)。
一些细节：
显然在 \([st+1,st+n]\) 之外的值无法贡献覆盖，所以需要在判断范围移动的时候撤销或添加右端点的覆盖。
\(st\) 可以为负数，所以需要将线段树加起始值防止越界。
复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back
typedef long long i64;
const int N = 150010;
int n, m, st, lim;
int a[N], buc[3 * N];
struct seg {
int mn;
int mncnt, ans;
int lzy;
} t[(3 * N) << 2];
void pushup(int u) {
t[u].ans = t[u << 1].ans + t[u << 1 | 1].ans;
t[u].mn = std::min(t[u << 1].mn, t[u << 1 | 1].mn);
t[u].mncnt = 0;
if(t[u].mn == t[u << 1].mn) t[u].mncnt += t[u << 1].mncnt;
if(t[u].mn == t[u << 1 | 1].mn) t[u].mncnt += t[u << 1 | 1].mncnt;
}
void build(int u, int l, int r) {
if(l == r) {
t[u] = {0, 1, 1, 0};
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void pushdown(int u) {
if(!t[u].lzy) return;
t[u << 1].mn += t[u].lzy, t[u << 1 | 1].mn += t[u].lzy;
t[u << 1].lzy += t[u].lzy, t[u << 1 | 1].lzy += t[u].lzy;
if(!t[u << 1].mn) t[u << 1].ans = t[u << 1].mncnt;
else t[u << 1].ans = 0;
if(!t[u << 1 | 1].mn) t[u << 1 | 1].ans = t[u << 1 | 1].mncnt;
else t[u << 1 | 1].ans = 0;
t[u].lzy = 0;
}
void update(int u, int l, int r, int L, int R, int x) {
if(L <= l && r <= R) {
t[u].mn += x;
t[u].lzy += x;
if(!t[u].mn) t[u].ans = t[u].mncnt;
else t[u].ans = 0;
return;
}
int mid = (l + r) >> 1;
pushdown(u);
if(L <= mid) update(u << 1, l, mid, L, R, x);
if(R > mid) update(u << 1 | 1, mid + 1, r, L, R, x);
pushup(u);
}
int query(int u, int l, int r, int L, int R) {
if(L <= l && r <= R) {
return t[u].ans;
}
int mid = (l + r) >> 1, ret = 0;
pushdown(u);
if(L <= mid) ret += query(u << 1, l, mid, L, R);
if(R > mid) ret += query(u << 1 | 1, mid + 1, r, L, R);
return ret;
}
void Solve() {
std::cin >> n >> m;
st = N - 10, lim = 3 * N - 30;
for(int i = 1; i <= n; i++) {
std::cin >> a[i];
a[i] += st;
buc[a[i]]++;
}
build(1, 1, lim);
for(int i = st + 1; i <= st + n; i++) {
if(buc[i]) update(1, 1, lim, i - buc[i] + 1, i, 1);
}
while(m--) {
int p, x;
std::cin >> p >> x;
if(p) {
if(a[p] <= st + n) {
update(1, 1, lim, a[p] - buc[a[p]] + 1, a[p] - buc[a[p]] + 1, -1);
}
buc[a[p]]--;
a[p] = st + x;
if(a[p] <= st + n) {
update(1, 1, lim, a[p] - buc[a[p]], a[p] - buc[a[p]], 1);
}
buc[a[p]]++;
} else {
if(x == 1) {
if(buc[st + n]) {
update(1, 1, lim, st + n - buc[st + n] + 1, st + n, -1);
}
st--;
}
else {
st++;
if(buc[st + n]) {
update(1, 1, lim, st + n - buc[st + n] + 1, st + n, 1);
}
}
}
std::cout << query(1, 1, lim, st + 1, st + n) << "\n";
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solve();
return 0;
}