题目概要
设 \(X = (X_1, \dots, X_M)\) 是一个长为 \(M\) 的非负整数序列。定义 \(\mex(X)\) 为未在 \(X\) 中出现的最小非负整数，例如 \(\mex((1,1,0)) = 2\)，\(\mex((3, 1)) = 0\)。由序列 \(X\) 通过下述方式可以得到的序列 \(Y = (Y_1, \dots, Y_M)\)：
- 选择一个长为 \(M\) 的正整数序列 \(D = (D_1, \dots, D_M)\)。
- 对每个 \(i = 1, \dots, M\)，定义 \(Y_i := X_i \bmod D_i\)。
定义 \(f(X)\) 为所有可能得到的序列 \(Y\) 的 \(\mex\) 值的最大值。
给你一个长为 \(N\) 的非负整数序列 \(A = (A_1, \dots, A_N)\)。
- easy version: 求 \(f(A)\)。
- hard version: 对每个 \(i = 1, \dots, N\)，求 \(f((A_1, \dots, A_i))\)。
限制：
- \(1 \le N \le 2\times 10^5\)
- \(0 \le a_i \le 10^6\)
观察
- 设 \(x, y\) 是正整数。如果 \(x \ge y\) 那么 \(x \bmod y < x/2\)。
证明：若 \(y \le x/2\)，则有 \(x \bmod y < y \le x/2\)。若 \(x / 2 < y \le x\)，则有 \(x \bmod y = x - y < x/2\)。
- \(Y_i\) 可以取集合 \(\set{X_i} \cup [0, X_i/2)\) 里的任何一个整数。
换言之，每个 \(A_i\) 要么不变，要么变成 \([0, A_i/2)\) 里的任何一个整数。
解法
easy version
考虑二分答案。对于给定的正整数 \(x\)（\(1 \le x \le N\)），我们想要判断
- 答案是否可能 \(\ge x\)？
也就是
- 能否把 \(0, 1, \dots, x - 1\) 都凑出来？
贪心地凑：
- 对于 \(0, 1, \dots, x - 1\) 中的每个整数 \(i\)，如果 \(A_1, \dots, A_N\) 这 \(N\) 个元素中有 \(i\)，那就拿一个 \(i\) 出来用。
- 剩下的问题是：用剩下元素能否把还缺的整数凑齐？
大元素去补大缺，小元素去补小缺。可以从小往大看：若剩下的最小元素不能去补最小的缺，就把这个元素扔掉，看下一个元素。也可以从大到小看：若剩下的最大元素不能去补最大的缺，那就凑不齐。
从小往大看
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a.begin(), a.end());
auto check = [&](int x) {
vector<bool> vis(x);
for (int y : a)
if (y < x)
vis[y] = true;
// 双指针
int j = 0;
// 从小往大看
for (int i = 0; i < x; i++) {
if (vis[i]) continue;
// 跳过用不上的元素
while (j < n &&
(a[j] <= 2 * i || a[j] < x && (j == 0 || a[j - 1] < a[j])))
j++;
if (j == n)
return false;
j++;
}
return true;
};
int ok = 1, ng = n + 1;
while (abs(ok - ng) > 1) {
int x = (ok + ng) / 2;
if (check(x))
ok = x;
else
ng = x;
}
cout << ok << '\n';
}从大往小看
auto check = [&](int x) {
vector<bool> vis(x);
for (int y : a)
if (y < x)
vis[y] = true;
// 双指针
int j = n - 1;
// 从大往小看
for (int i = x - 1; i >= 0; i--) {
if (vis[i]) continue;
while (j >= 0 && a[j] < x && (j == n - 1 || a[j] < a[j + 1]))
j--;
if (j < 0 || a[j] <= 2 * i)
return false;
j--;
}
return true;
};