---

1. 理解删空过程

删空规则：
当前数列长度为 $k$，就删除所有等于 $k$ 的数，然后长度变为 $k'$（剩余数字个数），继续删除等于 $k'$ 的数，直到空。

例如：$(1,2,3)$

• $k=3$，删除所有 $3$ → $(1,2)$
• $k=2$，删除所有 $2$ → $(1)$
• $k=1$，删除所有 $1$ → 空
  可以删空。

---

2. 可删空的充要条件

我们考虑一个长度为 $n$ 的数列 $a$ 可删空的条件。

设 $c[i]$ 表示数值 $i$ 在数列中出现的次数。

删空过程模拟：

• 初始长度 $n$，删除所有等于 $n$ 的数，剩余长度 $n' = n - c[n]$
• 接着删除所有等于 $n'$ 的数，剩余长度 $n'' = n' - c[n']$
• 依此类推。

如果过程中某一步 $k$ 在数列中不存在（$c[k] = 0$），就无法继续删除，除非我们提前修改一些数字。

---

2.1 关键观察

设 $f(k)$ = 在删除过程中，当需要删除数值 $k$ 时，这个数值在数列中出现的次数（包括之前修改过的）。

如果 $f(k) \ge 1$，这一步就能继续。
如果 $f(k) = 0$，我们就必须提前修改某个数，使其变成 $k$。

因此，最少修改次数 = 删除过程中遇到的 $f(k) = 0$ 的 $k$ 的个数。

但 $f(k)$ 是动态的，因为整体加减会影响数值。

---

3. 整体偏移的处理

设整体加的总和为 $delta$（可以为负）。
初始 $delta=0$，每次 $p=0, x=1$ 则 $delta += 1$，$x=-1$ 则 $delta -= 1$。

那么实际数值 $a_i$ 在比较时，应该用 $a_i' = a_i + delta$ 吗？
不对，因为删除规则中的 $k$ 是当前长度，不受整体加减影响。但数列中的数字受整体加减影响。

更准确地说：
设 $b_i = a_i - delta$ 是原始输入调整后的值（这样整体加减时 $b_i$ 不变）。
但单点修改时，修改的是 $a_i$ 而不是 $b_i$，所以 $b_i = a_i - delta$ 仍然成立。

那么比较时：
当前长度为 $k$，我们要看是否存在 $b_i + delta = k$ 的数，即 $b_i = k - delta$。

因此，定义 $cnt[v]$ 表示 $b_i = v$ 的个数（$v$ 范围可能很大，因为 $delta$ 会变）。

---

4. 转化为 $cnt$ 数组问题

设 $d = delta$（整体加减的偏移量）。

删除过程：

• 初始 $k = n$
• 若 $cnt[k-d] \ge 1$，则 $k \to k - cnt[k-d]$
• 否则，必须修改一次，$k \to k - 1$（因为我们修改一个数变成 $k-d$）

所以问题变成：
给定 $cnt$ 数组和 $d$，模拟删除过程，统计 $cnt[k-d] = 0$ 的次数。

---

5. 快速计算答案

直接模拟每次删除过程是 $O(n)$ 的，总复杂度 $O(nm)$ 不可行。

我们需要快速计算：

$$\text{ans} = \#\{ k \in S \mid cnt[k-d] = 0 \}$$

其中 $S$ 是删除过程中访问到的 $k$ 的集合。

---

5.1 删除路径的规律

删除过程是确定的：
$k_0 = n$
$k_{t+1} = k_t - \max(1, cnt[k_t - d])$
因为如果 $cnt[k_t-d] \ge 1$，就减 $cnt[k_t-d]$，否则减 1（修改一次）。

注意 $cnt[k_t-d] = 0$ 时，$k_{t+1} = k_t - 1$。
$cnt[k_t-d] \ge 1$ 时，$k_{t+1} = k_t - cnt[k_t-d]$。

---

5.2 关键优化

设 $need = k - d$。
当 $cnt[need] = 0$ 时，$k$ 会减少 1，然后 $need$ 也减少 1（因为 $k$ 减 1，$d$ 不变）。
所以一旦遇到一个 $cnt[need]=0$，就会连续递减直到遇到 $cnt[need] \ge 1$。

因此，连续的 $need$ 满足 $cnt[need]=0$ 的段 会对应一连串的修改。

---

5.3 转化为求第一个非零位置

我们从 $k=n$ 开始，$need = n-d$。
如果 $cnt[need] \ge 1$，则 $k$ 跳到 $k - cnt[need]$，$need$ 变成 $k - cnt[need] - d$。
如果 $cnt[need] = 0$，则这一段连续的 $0$ 都会导致修改，直到 $cnt[need] \ge 1$。

因此，问题变成：
从 $start = n-d$ 开始，每次遇到 $cnt[need]=0$，就沿着 $need$ 递减的方向走，直到遇到 $cnt[need] \ge 1$，然后跳过一段。

---

5.4 数据结构维护

我们需要快速查询：
给定 $start$，求最小的 $t \le start$ 使得 $cnt[t] \ge 1$，且知道 $t$ 之后可以跳到 $start' = t - cnt[t]$ 继续。

这相当于在 $cnt$ 数组上做“下一个非零位置”查询，并且支持单点更新（单点修改影响 $cnt[b_i]$）。

可以用并查集或链表维护每个位置的下一个非零位置。
具体地，维护 $next[v]$ 表示 $v$ 左边（包括 $v$）最近的非零 $cnt$ 的位置。
当 $cnt[v]$ 从 0 变成 1 时，合并区间；当 $cnt[v]$ 从 1 变成 0 时，拆分区间。

---

6. 算法步骤

1. 初始化 $delta=0$，$b_i = a_i$（因为初始 $delta=0$）。
2. 初始化 $cnt$ 数组（用字典或数组，范围 $[-m, n+m]$ 左右）。
3. 用并查集维护 $next$ 指针：$next[v]$ 指向 $v$ 左边最近的 $cnt>0$ 的位置，如果没有则为 $-\infty$。
4. 对于每次修改：
   • 如果是整体加减，更新 $delta$。
   • 如果是单点修改，更新 $cnt$ 和并查集。
5. 计算答案：
   从 $start = n - delta$ 开始，
   • 如果 $cnt[start] \ge 1$，则 $start \to start - cnt[start]$，继续。
   • 如果 $cnt[start] = 0$，则找到 $p = next[start]$，如果 $p$ 不存在（$p$ 太小），则从 $start$ 到 $1$ 都要修改，即 $start$ 次修改；否则从 $start$ 到 $p+1$ 这一段都是 0，修改次数 $start - p$，然后 $start \to p - cnt[p]$。
     重复直到 $start \le 0$，总修改次数就是答案。

---

7. 复杂度

• 每次查询答案的步数 ≤ 修改次数 + 1，因为每次跳跃至少减少 $1$ 的 $start$，并且遇到零段时直接跳到下一个非零位置。
• 并查集操作近似 $O(1)$。
• 总复杂度 $O((n+m) \alpha(n+m))$。

---

8. 代码框架（C++）

#include <bits/stdc++.h>
using namespace std;

const int MAX = 900005; // 范围 [-300000, 600000] 偏移 300000
const int OFFSET = 300000;

int n, m;
int delta;
int cnt[MAX];
int b[150005];
int parent[MAX];

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) parent[x] = y;
}

void add_val(int v) {
    v += OFFSET;
    cnt[v]++;
    if (cnt[v] == 1) {
        if (cnt[v-1] >= 1) unite(v-1, v);
        if (cnt[v+1] >= 1) unite(v, v+1);
    }
}

void remove_val(int v) {
    v += OFFSET;
    cnt[v]--;
    if (cnt[v] == 0) {
        parent[v] = v;
    }
}

int query_next(int v) {
    v += OFFSET;
    if (cnt[v] >= 1) return v - OFFSET;
    int p = find(v);
    if (p >= v) return -1e9; // 没有左边的非零
    return p - OFFSET;
}

int solve() {
    int start = n - delta;
    int ans = 0;
    while (start > 0) {
        int need = start;
        if (cnt[need + OFFSET] >= 1) {
            start -= cnt[need + OFFSET];
        } else {
            int p = query_next(need);
            if (p < -1e8) {
                ans += start;
                break;
            }
            ans += (need - p);
            start = p - cnt[p + OFFSET];
        }
    }
    return ans;
}

int main() {
    // 初始化 parent
    for (int i = 0; i < MAX; i++) parent[i] = i;

    scanf("%d%d", &n, &m);
    delta = 0;
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        b[i] = x;
        add_val(x - delta); // 初始 delta=0
    }

    for (int i = 0; i < m; i++) {
        int p, x; scanf("%d%d", &p, &x);
        if (p == 0) {
            // 整体加减
            if (x == 1) {
                delta++;
            } else {
                delta--;
            }
        } else {
            // 单点修改
            remove_val(b[p] - delta);
            b[p] = x;
            add_val(b[p] - delta);
        }
        printf("%d\n", solve());
    }
    return 0;
}

---

9. 总结

这道题的核心是将删空过程转化为对 $cnt$ 数组的跳跃查询，利用并查集维护连续零段的快速跳过，从而高效回答多次询问。