首先，不难发现，第一个被删的数一定为 (n) 然后被删的数一定为 (n - S_n)（(S_n) 为 (n) 出现过的次数）。
那么如果要一趟被删完当且仅当每个这样的过程都要接起来。
可以发现这是一个极为抽象的过程，可以考虑将这个抽象问题具体化。
可以想象一个二维平面，横坐标表示值域，纵坐标表示这个值域出现过的数，对于每个数 (i)，连一条 ((i, 0) ightarrow (i, S_i)) 的线段。
那么你可以发现，删掉 (n) 后删的数就是将 (x = n) 上的这条线段往左放倒后左端点所在的哪个点对应的数。
不难发现对于任意一个数它放倒的区间都是 ([i - S_i, i])。
进一步可以发现，如果一个序列是能恰好删完的，当且仅当恰好完全覆盖了 ([0, n]) 上的所有位置。
此时不难发现，原问题修改的下界应该至少是 ([0, n]) 中没有被覆盖的数量，显然的是，这个下界总是能达到的。
那么不带修的情况直接差分区间覆盖即可，下面来考虑待修的情况。
-
支持单点修改，不难发现本质上是将 (a_p) 的放倒区间左边缩减 (1)，将 (x) 的放倒区间左边增加 (1) 不难发现这是可以直接修改做到 (O(1)) 的。
-
支持整体 (+1/-1)，不难发现本质上是将刚刚的覆盖区间整体平移，只需要记录一个变化量即可。但是，当放倒区间的右端点到 (n) 右侧以后，他是不能对覆盖产生贡献的。（因为至少要把这些数全部改成 (n) 以下）。所以这种情况下需要支持某个右端点跨过 (n) 时将之前的贡献消除，不难发现使用线段树进行区间加减即可。
最后查询的时候只需要查询对应区间内 (0) 的数量，不难发现每个区间的最小值都不大于 (0)，直接维护最小值数量即可。
一些坑点
- 在 (
m pushup) 的时候一定不能直接返回左右儿子，因为此时会将左右儿子的懒标记一起返回。（
因为这个调了一晚上）
#include <bits/stdc++.h>
using namespace std;
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid (l + r >> 1)
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 6e5 + 5;
struct tree { int min, cnt, tag;} ans, t[N << 2];
int n, m, p, x, L, D, a[N], S[N];
int read() {
char c; int x = 0, f = 1;
c = getchar();
while (c > '9' || c < '0') { if(c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
tree chkmin(tree L, tree R) {
if(L.min < R.min) return (tree){L.min, L.cnt, 0};
else if(L.min > R.min) return (tree){R.min, R.cnt, 0};
else return (tree){L.min, L.cnt + R.cnt, 0};
}
void lazy(int p, int l, int r, int k) {
t[p].min += k, t[p].tag += k;
}
void down(int p, int l, int r) {
if(!t[p].tag) return;
lazy(ls, l, mid, t[p].tag), lazy(rs, mid + 1, r, t[p].tag);
t[p].tag = 0;
}
void build(int p, int l, int r) {
t[p].cnt = r - l + 1;
if(l == r) return;
build(ls, l, mid), build(rs, mid + 1, r);
}
void update(int p, int l, int r, int x, int y, int k) {
if(x > y) return;
if(l >= x && r <= y) { lazy(p, l, r, k); return;}
down(p, l, r);
if(mid >= x) update(ls, l, mid, x, y, k);
if(mid < y) update(rs, mid + 1, r, x, y, k);
t[p] = chkmin(t[ls], t[rs]);
}
tree query(int p, int l, int r, int x, int y) {
if(l >= x && r <= y) return t[p];
down(p, l, r);
tree ans = (tree){n + 1, 0, 0};
if(mid >= x) ans = chkmin(ans, query(ls, l, mid, x, y));
if(mid < y) ans = chkmin(ans, query(rs, mid + 1, r, x, y));
return ans;
}
int main() {
n = read(), m = read(), L = 2 * n + 2 * m;
rep(i, 1, n) a[i] = read() + n + m, ++S[a[i]];
build(1, 1, L);
rep(i, n + m + 1, n * 2 + m) update(1, 1, L, i - S[i] + 1, i, 1);
rep(i, 1, m) {
p = read(), x = read();
if(p) {
x += n + m;
if(a[p] + D <= n * 2 + m) update(1, 1, L, a[p] - S[a[p]] + 1, a[p] - S[a[p]] + 1, -1);
--S[a[p]];
++S[x - D];
update(1, 1, L, x - S[x - D] - D + 1, x - S[x - D] - D + 1, 1);
a[p] = x - D;
}
else {
if(x == -1) {
--D;
if(S[n * 2 + m - D]) update(1, 1, L, n * 2 + m - D - S[n * 2 + m - D] + 1, n * 2 + m - D, 1);
}
else {
if(S[n * 2 + m - D]) update(1, 1, L, n * 2 + m - D - S[n * 2 + m - D] + 1, n * 2 + m - D, -1);
++D;
}
}
ans = query(1, 1, L, n + m - D + 1, n * 2 + m - D);
printf("%d
", !ans.min ? ans.cnt : 0);
}
return 0;
}