题目内容
原题链接
给定一个长度为
n
n
n 的整数数组
a
a
a ，求所有长度为
m
m
m 的连续子数组的
m
e
x
mex
mex 最小值。
数据范围
1
≤
m
≤
n
≤
1.5
×
1
0
6
1\leq m\leq n\leq 1.5\times 10^6
1≤m≤n≤1.5×106
0
≤
a
i
<
n
0\leq a_i<n
0≤ai<n
题解
首先答案至多为
m
m
m ，因为一个长度为
m
m
m 的子数组，最多可以使得
0
0
0 到
m
−
1
m-1
m−1 都出现一次，此时答案最大，为
m
m
m 。
思路1：树状数组二分
维护每个数在个这个长度为
m
m
m 的子数组中是否出现，那么只需要求前
i
i
i 个下标的和是否等于
i
i
i 即可。这里需要把每个元素的值从
[
0
,
n
−
1
]
[0,n-1]
[0,n−1] 映射到
[
1
,
n
]
[1,n]
[1,n] 。
这里还可以进行的优化是答案至多为
m
m
m ，所以我们只需要考虑
[
0
,
m
−
1
]
[0,m-1]
[0,m−1] 的数即可。
时间复杂度：
O
(
n
log
2
n
)
O(n\log^2 n)
O(nlog2n)
代码1
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> cnt(n);
vector<int> tr(n + 1);
auto add = [&](int p, int x) {
while (p <= n) {
tr[p] += x;
p += (p & -p);
}
};
auto query = [&](int p) {
int res = 0;
while (p >= 1) {
res += tr[p];
p -= (p & -p);
}
return res;
};
int minv = n;
for (int i = 0; i < n; ++i) {
if (++cnt[a[i]] == 1) {
add(a[i] + 1, 1);
}
if (i >= m - 1) {
if (query(n) < n) {
int l = 1, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (query(mid) < mid) r = mid;
else l = mid + 1;
}
minv = min(minv, l - 1);
}
if (--cnt[a[i - m + 1]] == 0) {
add(a[i - m + 1] + 1, -1);
}
}
}
cout << minv << "\n";
return 0;
}
思路2：思维
本题是一个滑动窗口，每次窗口中会删去一个旧数
x
x
x，添加一个新数
y
y
y，所以这个窗口至多会两个数的变化。
当数
x
x
x 滑出这个窗口时，判断其在新窗口中是否存在，如果不存在，说明这个新的窗口的
m
e
x
mex
mex 至多为
x
x
x 。
这里我们考虑滑动窗口移动后，新的窗口中不再有
x
x
x 的情况，那么必然有
x
≠
y
x\neq y
x=y ，此时有如下两种情况：
-
x
<
y
x<y
x<y ，区间
m
e
x
mex
mex 可能减小，如果原区间的
m
e
x
x
>
x
mex_x>x
mexx>x ，那么新区间
m
e
x
y
=
x
mex_y=x
mexy=x ，否则区间
m
e
x
mex
mex 不变
-
x
>
y
x>y
x>y ，区间
m
e
x
mex
mex 可能增大，但是至多为
x
x
x
所以用
x
x
x 可以用来更新答案。
这里需要单独计算第一个区间
[
0
,
m
−
1
]
[0,m-1]
[0,m−1] 的
m
e
x
mex
mex
时间复杂度：
O
(
n
)
O(n)
O(n)
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> cnt(m);
// 先计算前 m 个数的 mex
for (int i = 0; i < m; ++i) {
if (a[i] < m) cnt[a[i]] += 1;
}
int ans = 0;
while (ans < m && cnt[ans] > 0) ans += 1;
for (int i = m; i < n; ++i) {
if (a[i] < m) cnt[a[i]] += 1;
if (a[i - m] < m) {
if (--cnt[a[i - m]] == 0) {
ans = min(ans, a[i - m]);
}
}
}
cout << ans << '\n';
return 0;
}
