在建设 OJ（在线评测系统）数据时，针对哈希表题目，我们需要特别构造哈希冲突压力测试、无解边缘测试以及 $k=0$ 的边界测试。

以下是为你准备的数据生成器源码。它包含了标准 $O(n)$ 逻辑并自动生成 1.in/1.out 到 10.in/10.out。

一、 数据生成器 (C++14)

#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <string>
#include <random>
#include <chrono>
#include <algorithm>

using namespace std;

// --- 标程：用于生成 .out 答案文件 ---
string getStandardOutput(int n, int k, const vector<int>& a) {
    if (k <= 0) return "NO"; // 步长为0或负，不可能存在两个不同下标
    unordered_map<int, int> last_pos;
    for (int i = 0; i < n; ++i) {
        if (last_pos.find(a[i]) != last_pos.end()) {
            if (i - last_pos[a[i]] <= k) return "YES";
        }
        last_pos[a[i]] = i;
    }
    return "NO";
}

// --- 数据生成逻辑 ---
void make_data() {
    // 高质量随机数引擎
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> val_dist(-1000000000, 1000000000);

    for (int t = 1; t <= 10; ++t) {
        int n, k;
        vector<int> a;

        // --- 针对性构造不同类型的测试点 ---
        if (t == 1) { // 边界：最小 n
            n = 1; k = 0;
            a = {val_dist(rng)};
        }
        else if (t == 2) { // 边界：k = 0
            n = 1000; k = 0;
            for(int i=0; i<n; ++i) a.push_back(1); // 全同但k=0应返回NO
        }
        else if (t == 3) { // 特殊：重复元素距离恰好为 k (YES)
            n = 10000; k = 500;
            for(int i=0; i<n; ++i) a.push_back(val_dist(rng));
            a[5000] = 777; a[5500] = 777;
        }
        else if (t == 4) { // 特殊：重复元素距离恰好为 k+1 (NO)
            n = 10000; k = 500;
            for(int i=0; i<n; ++i) a.push_back(val_dist(rng));
            int val = val_dist(rng);
            a[5000] = val; a[5000 + k + 1] = val;
            // 确保中间没有该值的干扰
        }
        else if (t == 5) { // 大规模：全不相同 (NO)
            n = 100000; k = 50000;
            unordered_map<int, bool> used;
            for(int i=0; i<n; ++i) {
                int v = val_dist(rng);
                while(used[v]) v = val_dist(rng);
                a.push_back(v);
                used[v] = true;
            }
        }
        else if (t == 6) { // 大规模：全部元素相同 (YES)
            n = 100000; k = 1;
            a.assign(n, 999);
        }
        else if (t == 7) { // 大规模：哈希冲突压力 (构造大量相同哈希值的数)
            n = 100000; k = 10;
            // 虽然不能直接构造哈希桶冲突，但可以通过构造大量重复值来压迫哈希表
            for(int i=0; i<n; ++i) a.push_back(rng() % 50); 
        }
        else if (t >= 8 && t <= 10) { // 满额规模：随机分布
            n = 100000; k = rng() % 100000;
            for(int i=0; i<n; ++i) a.push_back(val_dist(rng));
        }

        // --- 写入 .in 文件 ---
        string in_name = to_string(t) + ".in";
        ofstream fin(in_name);
        fin << n << " " << k << "\n";
        for (int i = 0; i < n; ++i) {
            fin << a[i] << (i == n - 1 ? "" : " ");
        }
        fin << "\n";
        fin.close();

        // --- 调用标程生成 .out 文件 ---
        string out_name = to_string(t) + ".out";
        ofstream fout(out_name);
        fout << getStandardOutput(n, k, a) << endl;
        fout.close();

        cout << "Generated Case " << t << ": n=" << n << ", k=" << k << endl;
    }
}

int main() {
    make_data();
    cout << "\nAll test cases generated successfully!" << endl;
    return 0;
}

二、 测试点规划说明 (OJ 建设参考)

三、 生成器设计要点总结

1. 非递归与内存安全： 所有逻辑都在迭代循环中完成，数据存储使用 std::vector。由于 vector 数据存储在堆上，即使 $N=10^5$ 对应 400KB，也远低于系统限制，不会爆栈。
2. 时间复杂度优化： 生成器内部的标程采用了 unordered_map 的 $O(n)$ 算法。生成 10 组满额数据总耗时约在 0.5 秒左右（取决于机器性能），确保创建数据时不会超时。
3. 负数与大数覆盖： 使用了 uniform_int_distribution<int> (-1e9, 1e9)，确保测试数据涵盖了所有合法的 int 范围，防止选手使用数组计数等错误方法。
4. 符合规范： 输出严格遵循 NOI 格式：第一行两个整数，第二行 $n$ 个数由空格分隔，行末无多余空格，文件以换行符结尾。

教练提示：在创建 OJ 数据时，建议将测试点 7 设置为重点。如果选手的哈希函数写得不好（如直接用原值做哈希且没处理好分布），或者使用了不当的动态数组，这一测试点很容易出现超时（TLE）。加油！

这是“存在重复元素 II”问题的标准题解。在 NOI 竞赛中，此题是练习散列表（Hash Map）与单指针维护状态的极佳案例。

一、 题解标准代码 (C++14)

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

/**
 * 核心逻辑：
 * 遍历数组，利用哈希表存储每个数值“最后一次出现的位置（下标）”。
 * 当遇到数值 x 时，检查哈希表中是否存在 x：
 * 1. 若存在，计算当前下标 i 与上次下标 last_pos 的差值。
 * 2. 若差值 <= k，则找到满足条件的对，直接返回结果。
 * 3. 无论是否存在，都更新哈希表中 x 的下标为当前 i（因为靠后的下标更有可能满足后续的距离约束）。
 */

int main() {
    // 竞赛优化：加速 I/O 性能
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    if (!(cin >> n >> k)) return 0;

    // unordered_map 在 C++14 中平均查找时间为 O(1)
    // key: 数组元素的值, value: 该值最近一次出现的下标
    unordered_map<int, int> last_pos;
    
    // 优化：预先分配哈希表空间，减少动态扩容带来的常数开销
    last_pos.reserve(n);

    bool found = false;
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;

        // 如果已经找到了，仅继续读完输入（或者在多组数据时注意处理）
        if (found) continue; 

        // 检查当前值是否在之前出现过
        // last_pos.count() 或 last_pos.find() 均可
        if (last_pos.find(val) != last_pos.end()) {
            // 易错点：计算距离时，i 是当前的，last_pos[val] 是最近的
            if (i - last_pos[val] <= k) {
                found = true;
            }
        }
        
        // 关键点：无论是否触发距离约束，都要更新当前值的最新下标
        // 这样可以保证后续比对时，距离差值是最小的（即最容易满足 <= k）
        last_pos[val] = i;
    }

    if (found) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度分析

• 扫描过程：数组遍历一次，复杂度 $O(n)$。
• 哈希操作：unordered_map 的 find 和插入操作在平均情况下均为 $O(1)$。
• 结论：总时间复杂度为 平均 $O(n)$。
  • 对于 $n = 10^5$，运算量约为 $10^5$ 次哈希操作，能在 0.1s 内轻松完成。

2. 空间复杂度分析

• 存储开销：最坏情况下（没有重复元素），哈希表需要存储 $n$ 个不同的键值对。
• 结论：总空间复杂度为 $O(n)$。
  • $10^5$ 个键值对（每个包含两个 int）约占用几 MB 内存，远小于竞赛 128MB 的标准限制。

三、 时间复杂度优化建议

尽管 $O(n)$ 已是理论最优，但在 NOI 实际评测中，unordered_map 可能遇到以下问题及优化方案：

1. 防止哈希冲突攻击（Anti-Hash Test Cases）：

   • 风险：某些评测数据可能特制大量的哈希冲突，使 unordered_map 的复杂度退化为 $O(n^2)$。
   • 对策：可以使用自定义哈希函数（引入随机种子）或者使用 std::map（基于红黑树，$O(n \log n)$ 且非常稳定）。
   • 代码示例（自定义哈希）：

     struct custom_hash {
         static uint64_t splitmix64(uint64_t x) {
             x += 0x9e3779b97f4a7c15;
             x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
             x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
             return x ^ (x >> 31);
         }
         size_t operator()(uint64_t x) const {
             static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
             return splitmix64(x + FIXED_RANDOM);
         }
     };
     unordered_map<int, int, custom_hash> last_pos;
     

2. 固定大小滑动窗口（空间优化）：

   • 思路：如果 $k$ 远小于 $n$，我们其实只需要维护一个大小为 $k$ 的哈希集合（unordered_set）。
   • 做法：遍历时将 $A[i]$ 放入集合，当 $i > k$ 时，将 $A[i-k-1]$ 从集合中删除。
   • 优点：空间复杂度降为 $O(\min(n, k))$。

四、 总结：避坑指南

1. 下标 0 与默认值：
   • 如果使用 last_pos[val] 直接访问，若 val 不存在，它会默认创建并返回 0。这在下标本身从 0 开始时会产生逻辑歧义。
   • 建议：始终使用 find() 或 count() 先进行存在性检查。
2. $k=0$ 的判定：
   • 如果 $k=0$，根据题目要求 $|i-j| \le 0$ 且 $i \neq j$，这在数学上是不可能的。代码逻辑中 i - last_pos[val] <= 0 且 i > last_pos[val] 也会自然处理此情况。
3. 大整数处理：
   • 虽然元素值是 $10^9$，但下标差 $k$ 是 $10^5$。计算 $i - j$ 不会溢出 int，无需使用 long long。

教练点评： 这道题展示了如何利用附加数据结构（哈希表）来记录历史状态。在 NOI 中，这种“边走边查”的动态处理思路比先存下来再处理要高效得多。加油！