The 2025 ICPC 德国 German Collegiate Programming Contest——M. Mex Hex（使用区间维护可行域） · znzryb
## 题目大意
**题目大意**
有一只魔法山猫会对你进行 $n$ 次攻击，每次攻击有一个潜能值 $p_i$。你最终受到的痛苦值为所有**未被防御**的攻击潜能值的 $\text{mex}$（即未出现在这些潜能值集合中的最小自然数）。
你拥有一个盾牌，激活后可以持续防御接下来的 $d$ 次攻击。盾牌失效后会强制进入冷却，冷却时间同样持续 $d$ 次攻击，冷却期间无法再次激活。你可以多次激活盾牌，最早可以在第 1 次攻击前激活。
请制定最佳防御策略，使得受到的痛苦值最小。
**输入格式**
第一行包含两个整数 $n$ 和 $d$ ($1 \le n \le 10^5$, $1 \le d \le n$)，分别表示攻击总数和盾牌持续/冷却时间。
第二行包含 $n$ 个整数 $p_1, \dots, p_n$ ($0 \le p_i < n$)，表示每次攻击的潜能值。
**输出格式**
输出一个整数，表示可以达到的最小痛苦值。
**样例 1**
```
5 1
0 1 0 1 0
```
```
0
```
**解释**：$d=1$。可以在第 1、3、5 次攻击时激活盾牌（防御区间为 $[1,1], [3,3], [5,5]$），冷却区间为 $[2,2], [4,4]$。此时只有潜能为 1 的攻击击中你，$\text{mex}(\{1, 1\}) = 0$。
**样例 2**
```
5 2
0 1 0 1 0
```
```
2
```
**解释**：$d=2$。无论如何安排，冷却期间总会漏掉潜能为 0 和 1 的攻击。击中你的集合包含 $\{0, 1\}$，$\text{mex} \ge 2$。
**样例 3**
```
14 2
8 1 1 0 0 2 0 1 2 1 0 6 4 2
```
```
2
```
可以像图上一样防御。
**样例 4**
```
4 2
0 1 2 0
```
```
1
```
**解释**：最早只能在第 1 次攻击前激活，无法同时防御住第 1 个和第 4 个潜能为 0 的攻击（因为防御完第 1 个后，盾牌在第 2、3 个攻击期间防御，第 4 个攻击时可能刚结束或者在冷却，取决于具体激活时机，但无法跨越防御第 1 个和第 4 个而不防御中间的）。选择防御第 2、3 个攻击，漏掉第 1、4 个攻击（潜能均为 0），$\text{mex}(\{0, 0\}) = 1$。
## 思路讲解
这道题目其实不是很难，其实就是维护一下可行域就可以了。
那么初始的可行域是从一，就是**初始的可行域的左起点是 Max 一和 P 减 d 加一**。**右起点就是 P**。然后在**后面的过程**当中，我们去**不断的更新左起点**。一旦当**左起点它比右起点还大的时候**，左起点比右起点大的时候呢，这个时候就说明我们需要**新开一个区间了**。然后我们新开区间的左起点，就是可行域的左端点，就是 L 加2乘以 d 和 P 减 d 加一中取一个 max 如果说然后这个可行域的 R 就是 P 。如果说 L 大于 R 那就说明就进不了可行域。就这个是错的，就 return false 就好了。
```cpp
// 哦，这道题目的难点就在于这个 check 函数
// 负责检查该 VAL 是否可以被我们的防御魔法所全部覆盖
auto check=[&](ll val) -> bool {
if (g[val].empty()) {
return true;
}
// 维护一段可行起点区间
// 下面是起始的可行域。
ll l=max(1ll,g[val][0]-D+1),r=g[val][0];
for (int i=1;i<g[val].size();++i) {
ll p=g[val][i];
ll to_l=max(l,p-D+1);
// 我们先要检查一下这个 L 啊，这个 L 如果超过这个 R 了以后，我们就需要新建一段区间了。
if (to_l>r) {
l=max(l+2*D,p-D+1);
r=p;
if (l>r) {
return false;
}
}else {
l=to_l;
}
}
return true;
};
```
## AC代码
AC
[https://qoj.ac/submission/2032675](https://qoj.ac/submission/2032675)
AC
[https://codeforces.com/gym/106129/submission/362772763](https://codeforces.com/gym/106129/submission/362772763)
::: 源代码
```cpp
/**
* Problem: M. Mex Hex
* Contest: 2025
* Judge: Codeforces
* URL: https://codeforces.com/gym/106129/problem/M
* Created: 2026-02-13 14:06:03
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll N,D;
cin >> N >> D;
vector<ll> A(N+2);
vector<vector<ll>> g(N+2);
set<ll> st_mex;
for (int i=0;i<N;++i) {
st_mex.insert(i);
}
for (int i=1;i<=N;++i) {
cin>>A[i];
st_mex.erase(A[i]);
g[A[i]].push_back(i);
}
ll mex=*st_mex.begin();
if (mex==0) {
cout<<0<<"\n";
return;
}
// 哦，这道题目的难点就在于这个 check 函数
// 负责检查该 VAL 是否可以被我们的防御魔法所全部覆盖
auto check=[&](ll val) -> bool {
if (g[val].empty()) {
return true;
}
// 维护一段可行起点区间
ll l=max(1ll,g[val][0]-D+1),r=g[val][0];
for (int i=1;i<g[val].size();++i) {
ll p=g[val][i];
ll to_l=max(l,p-D+1);
// 我们先要检查一下这个 L 啊，这个 L 如果超过这个 R 了以后，我们就需要新建一段区间了。
if (to_l>r) {
l=max(l+2*D,p-D+1);
r=p;
if (l>r) {
return false;
}
}else {
l=to_l;
}
}
return true;
};
for (ll i=0;i<mex;++i) {
if (check(i)) {
cout<<i<<"\n";
return;
}
}
cout<<mex<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://qoj.ac/submission/2032675
AC
https://codeforces.com/gym/106129/submission/362772763
*/
```
:::
## 心路历程（WA，TLE，MLE……）
这个 check 函数是负责什么呢？是负责检查该 VAL 是否可以被我们的防御魔法所全部覆盖。直接采用这个贪心啊，它其实是没那么简单的。因为虽然说第一个我们肯定是要覆盖的，但是呢我们并不一定要在第一个位置就启用这个防御魔法，我们可以在其更前面的位置启用这个防御魔法。
```cpp
// 哦，这道题目的难点就在于这个 check 函数
auto check=[&](ll val) {
ll st=-INF;
for (auto p:g[val]) {
if (p-st+1<=D) {
continue;
}
if (p-st+1<=2*D) {
return false;
}
st=p;
}
return true;
};
```