题意
给定 \(n\) 个球，每个球上有一个数字 \(a_i\)。
每当魔法少女施展魔法时，会将写着当前球的数量的球全部消除。
\(q\) 次修改球的值，你需要在基础上修改最小的次数使得这 \(n\) 个球可以被魔法少女消除，求出你修改的最小次数。
\(n \le 2 \times 10 ^ 5\)。
Sol
神题！
由于修改至多一个球，因此答案至多变化 \(1\)。
没用。
考虑按照 \(a_i\) 的大小排序，将每类球合并，设 \(i\) 类球的个数为 \(a'_i\)，可以得到：\(i = \sum_{j < i} a'_j\)。
也就是说，第 \(i\) 类球恰好占满了上一个有球的位置 \(j\) 到 \(i\) 的空位，即 \([j + 1, i]\)。
注意到这 \(n\) 类球恰好有 \(n\) 个，恰好占满了 \(n\) 个位置，因此显然操作次数的下界就为空位数。
做完了，开个桶记录一下每个下标球的个数即可。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
using namespace std;
#ifdef ONLINE_JUDGE#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;#endif
int read() {int p = 0, flg = 1;char c = getchar();while (c < '0' || c > '9') {if (c == '-') flg = -1;c = getchar();}while (c >= '0' && c <= '9') {p = p * 10 + c - '0';c = getchar();}return p * flg;
}
void write(int x) {if (x < 0) {x = -x;putchar('-');}if (x > 9) {write(x / 10);}putchar(x % 10 + '0');
}
bool _stmer;const int N = 2e5 + 5;array <int, N> isl, idx;
array <int, N> s;bool _edmer;
int main() {cerr << (&_stmer - &_edmer) / 1024.0 / 1024.0 << "MB\n";int n = read(), q = read(), ans = n;for (int i = 1; i <= n; i++) {s[i] = read(), idx[s[i]]++;if (s[i] - idx[s[i]] >= 0) {if (!isl[s[i] - idx[s[i]]]) ans--;isl[s[i] - idx[s[i]]]++;}}while (q--) {int x = read(), y = read();if (s[x] - idx[s[x]] >= 0) {isl[s[x] - idx[s[x]]]--;if (!isl[s[x] - idx[s[x]]]) ans++;}idx[s[x]]--;s[x] = y;idx[s[x]]++;if (s[x] - idx[s[x]] >= 0) {if (!isl[s[x] - idx[s[x]]]) ans--;isl[s[x] - idx[s[x]]]++;}write(ans), puts("");}return 0;
}
