问题重述与核心转化

给定一个长度为 n 的整数序列 a，以及两个整数 K 和 D。我们需要找出有多少个不同的连续子区间 [l, r]，同时满足以下两个条件：

种类数限制：区间内不同数字的个数恰好为 K。
极差限制：区间内最大值与最小值的差（即极差）不超过 D。
直接计算“恰好包含 K 种不同数字”的区间数量逻辑较为复杂。这里我们引入容斥原理，将问题巧妙转化：

恰好包含 K 种 = 至多包含 K 种 - 至多包含 (K-1) 种

这样，我们将一个复杂问题分解为两个结构完全相同、更容易解决的子问题。接下来，我们只需解决一个通用子问题：“计算不同数字种类数至多为 limit_k，且极差不超过 D 的子区间数量”。

核心算法：滑动窗口与单调性分析

对于上述子问题，我们可以使用滑动窗口（双指针）算法来高效求解。滑动窗口算法之所以能够成立且高效，根本原因在于指针单调移动时，窗口内部状态（不同值数量、极值）具有严格的单调变化趋势。

1. 端点移动与“不同值数量”的单调性

右指针 right 向右移动（窗口扩张）：新元素进入窗口，窗口内不同值的数量 size 只会增加或保持不变，绝对不会减少。
左指针 left 向右移动（窗口收缩）：元素离开窗口，窗口内不同值的数量 size 只会减少或保持不变，绝对不会增加。

2. 端点移动与“极值（最大值、最小值）”的单调性

右指针 right 向右移动（窗口扩张）：新加入的元素可能比当前最大值还大，也可能比当前最小值还小。因此，最大值可能变大（绝不会变小），最小值可能变小（绝不会变大）。综合来看，极差（最大值 - 最小值）可能变大，也可能保持不变。
左指针 left 向右移动（窗口收缩）：被移出的元素如果恰好是窗口内唯一的最大值或最小值，极值会发生改变。因此，最大值可能变小（绝不会变大），最小值可能变大（绝不会变小）。综合来看，极差可能变小，也可能保持不变。

3. 单调性对算法的支撑
理解了上述趋势，滑动窗口的逻辑便顺理成章：

触发收缩：当右指针 right 向右移动一步后，由于扩张带来的单调性，种类数或极差可能变大，导致窗口变得“不合法”（即 size > limit_k 或 极差 > D）。
安全收缩：因为左指针 left 向右移动时，种类数和极差都呈现单调递减（或不变）的趋势，所以我们可以放心地不断向右移动 left，直到窗口重新回到合法状态，这样也就意味着我们可以轻松的统计至多的问题。
结果统计：因为 left 是单调递增的，对于当前的 right，我们找到的 left 一定是满足条件的最左边界。这也保证了以 right 为右端点的合法区间数量恰好是 right - left + 1，不会漏算也不会多算。

算法流程

基于上述单调性，算法的具体执行流程如下：

初始化左指针 left = 0，并使用一个有序容器（如 map，在map里的大小就是不同值的数量，并且map是有序的可以节约我们的极值查询时间）维护当前窗口内的数字及其出现次数。
遍历右指针 right 从 0 到 n-1，将 a[right] 加入窗口。
检查当前窗口是否合法。如果不合法，则不断将 a[left] 移出窗口并右移 left，直到窗口重新满足“种类数 ≤ limit_k 且极差 ≤ D”的条件。
当窗口合法时，累加当前右端点对应的合法子区间数量：count += (right - left + 1)。
最终，通过 atMostK(K) - atMostK(K-1) 得到最终答案。

易错点与注意事项

1.limit_k < 0 的边界检查：当 K=0 时，会调用 atMostK(n, -1, D)。必须在此处进行边界拦截并直接返回 0，否则会导致后续逻辑出错。
2.空容器访问：在计算极差时，必须先判断窗口是否为空（!window.empty()）。对空容器调用获取最大/最小值的操作会导致程序崩溃。
3.数据类型溢出：
结果计数：子区间的数量可能非常大，必须使用 long long 来存储结果。
极差计算：题目中的灵能值范围可能很大，两个 int 相减的结果也可能超出 int 范围。在计算极差时，必须先将其转换为 long long 再进行减法运算。
4.容器的更新与删除：当左指针移动时，如果某个数字的计数减为 0，必须从容器中彻底删除该键值对。否则，容器的大小将无法正确反映窗口内不同数字的真实种类数。
5.注意多组测试数据

完整代码

#include <iostream>
#include <vector>
#include <map>
using namespace std;
const int MAXN = 500005;
int a[MAXN]; 
long long atMostK(int n, int limit_k, int D) {
    if (limit_k < 0) return 0;
    long long count = 0;
    int left = 0;
    map<int, int> window; 
    for (int right = 0; right < n; right++) {
        window[a[right]]++;
        while (window.size() > (size_t)limit_k ||
            (!window.empty() && (long long)window.rbegin()->first - window.begin()->first > D)) {
            int val_to_remove = a[left];
            auto it = window.find(val_to_remove);
            if (it != window.end()) {
                it->second--;
                if (it->second == 0) {
                    window.erase(it);
                }
            }
            left++;
        }
        count += (right - left + 1);
    }
    return count;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n, K, D;
        cin >> n >> K >> D;
        
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        long long ans = atMostK(n, K, D) - atMostK(n, K - 1, D);
        cout << ans << "\n";
    }
    return 0;
}

河南萌新联赛2026第（一）场：河南工业大学E题题解