当前位置：首页 > news >正文

Codeforces Round 1054 (Div. 3) E题

news 2026/5/13 16:27:33

题目
https://codeforces.com/problemset/problem/2149/E

题目复盘：恰好 K 个不同数字 + 长度限制的子数组计数

理解题目

我们有一个长度为 n 的数组，每个位置是一个整数。
现在要统计有多少个连续子数组，同时满足两个条件：

不同数字的个数恰好等于 k
子数组的长度在 [l, r] 之间

看到这种题，很容易就往双指针上想，方向是对的但是怎么实现呢？

难点在哪

如果只有“恰好 k 个不同数字”，滑动窗口可以直接维护左指针，保证窗口内不同数字个数 ≤ k，然后再想办法统计恰好为 k 的区间。

但现在多了一个长度限制 [l, r]，窗口的大小不能再随意收缩：

收缩过头，长度可能小于 l，不满足条件。
扩张太多，长度可能超过 r，也不满足条件。

这意味着，对于固定的右端点 i，合法的左端点必须同时落在两个区间里。

Hint：用“至多”表示“恰好”

经典套路：

恰好 k 个 = 至多 k 个 − 至多 (k−1) 个

为什么呢？

“至多 k 个”的区间集合，包含“恰好 k 个”和“不同数字少于 k 个”的区间。
“至多 k−1 个”的区间集合，只包含“不同数字少于 k 个”的区间。
两者相减，剩下的就是“恰好 k 个”。

于是问题转化为：
统计每个右端点 i，有多少左端点 L 使得：

[L, i] 内不同数字 ≤ k （集合 A）
[L, i] 内不同数字 ≤ k−1 （集合 B）
长度在 [l, r] 之间

那么该右端点的贡献 = 同时满足条件 1 和长度限制的左端点位置 − （同时满足条件 2 和长度限制的左端点位置-1）。（不同数字恰好为 k,不能到 k - 1 所以为 ptr_k1-1）
即为当前右端点满足恰好为k的的合法贡献

双指针怎么移?

用两个滑动窗口，分别维护：

窗口 A：不同数字 ≤ k
窗口 B：不同数字 ≤ k−1

每个窗口都有一个左指针 ptr：

随着右端点 i 右移，新元素加入窗口。
若窗口内不同数字个数超过了上限，就不断移动左指针，踢出元素，直到重新满足 ≤ 上限。

维护完成后：

窗口 A 的左指针 ptr_k 表示：所有左端点 L ∈ [ptr_k, i]，保证不同数字 ≤ k。
窗口 B 的左指针 ptr_k1 表示：所有左端点 L ∈ [ptr_k1, i]，保证不同数字 ≤ k−1。

那么“恰好 k 个不同数字”的左端点范围就是：

[ptr_k, ptr_k1 - 1]

（这里假设 ptr_k ≤ ptr_k1 - 1，否则不存在）

怎么再加上长度限制

对于右端点 i，子数组长度为 i - L + 1。
要求 l ≤ i - L + 1 ≤ r，可以得出 L的范围：

i - r + 1 ≤ L ≤ i - l + 1

所以合法的 L 必须落在：

长度区间  = [i - r + 1, i - l + 1]
恰好k区间 = [ptr_k, ptr_k1 - 1]

两者取交集即可：

有效左端点下界 = max(ptr_k, i - r + 1)
有效左端点上界 = min(ptr_k1 - 1, i - l + 1)

如果下界 ≤ 上界，那么合法的左端点个数就是 上界 - 下界 + 1。

这样，我们对每个 i 计算贡献，累加就得到答案。

我们很快就能给出代码：

点击查看代码

//
// Created by awake on 2026/5/13.
//https://codeforces.com/problemset/problem/2149/E
#include <bits/stdc++.h>
using namespace std;// clang-format off
struct { auto operator()(auto &i) { cin >> i; } } IN; // NOLINT
struct { auto operator()(auto &i) { cout << i << ' '; } } OUT; // NOLINT
// clang-format on
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr)// NOLINT
using pii = pair<int, int>; //NOLINT
using ll = long long;       //NOLINT
template <typename T>
using vec = vector<T>; //NOLINT
// #define int long long
// #define endl '\n'
constexpr int INF = 0x3f3f3f3f;
constexpr int MOD = 998244353;
constexpr int N = 1e6 + 5;void solve()
{int n, k, l, r;cin >> n >> k >> l >> r;vec<int> a(n);ranges::for_each(a, IN);map<int, int> cntk;map<int, int> cntk1;int ptr_k = 0;int ptr_k1 = 0;ll ans = 0;for (int i = 0; i < n; i++){cntk[a[i]]++;cntk1[a[i]]++;while (cntk.size() > k){if (cntk[a[ptr_k]]--; cntk[a[ptr_k]] == 0)cntk.erase(a[ptr_k]);ptr_k++;}while (cntk1.size() > k - 1){if (cntk1[a[ptr_k1]]--; cntk1[a[ptr_k1]] == 0)cntk1.erase(a[ptr_k1]);ptr_k1++;}int left_k = max(ptr_k, i - r + 1);int left_k1 = min(ptr_k1 - 1, i - l + 1);//[ptr_k, ptr_k1 - 1] （不同数字恰好为 k,不能到 k - 1 所以为 ptr_k1-1）//[i - r + 1, i - l + 1] （长度在 [l, r]）if (left_k1 >= left_k)ans += left_k1 - left_k + 1;}cout << ans << endl;
}signed main()
{IOS;int T;cin >> T;while (T--)solve();return 0;
}