你好！我是金牌教练。为了帮助你精准地创建 OJ（在线判题系统）测试数据，我为你编写了这个集成化的数据生成器与标程（Generator & Solver）。

这个程序将生成 10 组测试数据。对于本题，$O(N)$ 的线性扫描在 $10^5$ 数据量下通常能跑过 1 秒。但在 NOI 竞赛中，如果题目明确要求 $O(\log N)$，我们通常会通过多组询问（虽然本题原题是单次询问）或极短的时限（如 0.1s）来强制要求二分。

这里我通过构造大规模重复数据和边界分布数据来确保二分逻辑的严谨性。

一、 测试点设计矩阵

二、 数据生成器 C++ 代码

该程序采用 C++14 标准，包含了生成输入文件和利用标程生成输出文件的完整逻辑。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <algorithm>
#include <ctime>

using namespace std;

typedef long long ll;

// --- 标程：双二分 O(log N) ---
pair<int, int> solve(int n, int target, const vector<int>& nums) {
    if (n == 0) return {-1, -1};
    
    int first = -1, last = -1;
    
    // 找左边界
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] >= target) {
            if (nums[mid] == target) first = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    
    // 找右边界
    l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] <= target) {
            if (nums[mid] == target) last = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    
    return {first, last};
}

// --- 数据生成逻辑 ---
void make_data() {
    mt19937 rng(time(0));
    uniform_int_distribution<int> dist_large(-1e9, 1e9);

    for (int t = 1; t <= 10; t++) {
        string in_name = to_string(t) + ".in";
        string out_name = to_string(t) + ".out";
        ofstream fout(in_name);
        ofstream fans(out_name);

        int n, target;
        vector<int> nums;

        if (t <= 2) { // 小规模
            n = (t == 1 ? 10 : 100);
            target = rng() % 20;
            for(int i=0; i<n; i++) nums.push_back(rng() % 20);
            sort(nums.begin(), nums.end());
        } 
        else if (t == 3) { // 空数组
            n = 0; target = 0;
        } 
        else if (t == 4) { // Target 太小
            n = 100000; target = -1e9;
            for(int i=0; i<n; i++) nums.push_back(dist_large(rng) % 500000000 + 500000000); // 均大于0
            sort(nums.begin(), nums.end());
        }
        else if (t == 5) { // Target 太大
            n = 100000; target = 1e9;
            for(int i=0; i<n; i++) nums.push_back(dist_large(rng) % 500000000); // 均小于 1e9
            sort(nums.begin(), nums.end());
        }
        else if (t == 6) { // 全部相等
            n = 100000; target = 888;
            nums.assign(n, 888);
        }
        else if (t == 7) { // 仅在头部
            n = 100000; target = 1;
            nums.push_back(1);
            for(int i=1; i<n; i++) nums.push_back(rng() % 1000000 + 2);
            sort(nums.begin(), nums.end());
        }
        else if (t == 8) { // 仅在尾部
            n = 100000; target = 1000000;
            for(int i=0; i<n-1; i++) nums.push_back(rng() % 1000000);
            nums.push_back(1000000);
            sort(nums.begin(), nums.end());
        }
        else if (t == 9) { // 缺失于中间
            n = 100000; target = 500;
            for(int i=0; i<n/2; i++) nums.push_back(rng() % 499);
            for(int i=n/2; i<n; i++) nums.push_back(rng() % 499 + 501);
            sort(nums.begin(), nums.end());
        }
        else { // 大规模随机
            n = 100000; target = dist_large(rng);
            for(int i=0; i<n; i++) nums.push_back(dist_large(rng));
            sort(nums.begin(), nums.end());
        }

        // 输出 .in
        fout << n << " " << target << "\n";
        for (int i = 0; i < n; i++) {
            fout << nums[i] << (i == n - 1 ? "" : " ");
        }
        fout << endl;

        // 计算并输出 .out
        pair<int, int> res = solve(n, target, nums);
        fans << res.first << " " << res.second << endl;

        cout << "Case " << t << " done. (n=" << n << ")" << endl;
        fout.close(); fans.close();
    }
}

int main() {
    make_data();
    return 0;
}

三、 生成器设计要点说明

1. 文件大小控制：

   • 对于 $n=10^5$ 的测试点，数组中每个数字加上空格平均按 10 字节计算，.in 文件大小约为 1MB。
   • 10 个测试点总大小约 8MB，完全符合 OJ 理想的存储限制。

2. 复杂度区分度：

   • 线性扫描 $O(N)$：虽然在 $10^5$ 数据下能过，但如果选手的二分逻辑写成“找到一个点后再左右线性探测”，在测试点 6（全数组相等）下，其局部探测的复杂度会退化到 $O(N)$。如果时限设为 0.1s，这种“伪二分”会超时。
   • 纯二分 $O(\log N)$：无论数据分布如何，均能在 1ms 内完成。

3. 边界覆盖：

   • $n=0$：测试选手是否处理了空输入。
   • 首尾位置：测试二分边界 l 和 r 的收缩是否会导致数组越界。
   • 不存在的情况：测试 ans 初始值及更新逻辑。

4. 稳定性：

   • 使用了 std::sort 确保输入始终满足“非递减顺序”的前提条件。
   • 二分部分采用 l + (r - l) / 2 避免大整数加法溢出。
   • 不涉及除法操作，无除零风险。

四、 如何使用

1. 将上述代码保存为 gen.cpp。
2. 使用 g++ gen.cpp -o gen -std=c++14 编译。
3. 运行 ./gen，当前目录下将自动生成 1.in/out 到 10.in/out。
4. 将这些文件压缩上传到你的 OJ 题目数据管理页面。

你好！我是金牌教练。在处理排序数组的检索问题时，从线性扫描到对数级别的二分，是每一个竞赛选手必须跨越的思维阶梯。

下面我为你演示这道题的代码演进。在 NOIP/NOI 考场上，根据数据范围选择最稳妥的实现是拿高分的关键。

版本 1：暴力扫描版 (Linear Scan)

思路： 最直观的方法。既然数组是有序的，目标元素一定连在一起。我们只需从左往右扫一遍，记录第一次看到 target 的位置和最后一次看到的位置。

复杂度分析：

• 时间复杂度：$O(n)$。在 $n=10^5$ 的情况下，大约需要 $10^5$ 次运算，在 1s 时限内完全没问题。但在更高要求的 $10^7$ 或强制要求 $\log n$ 的题目中会扣分。
• 空间复杂度：$O(n)$（存储输入数组）。

/*
 * 适用场景：n <= 10^6，且题目没有强制 $O(\log n)$ 要求时。
 * 优点：代码极短，不会写错。
 * 易错点：数组为空 (n=0) 时的特殊处理。
 */
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, target;
    if (!(cin >> n >> target)) return 0;
    
    vector<int> nums(n);
    int first = -1, last = -1;
    
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        if (nums[i] == target) {
            if (first == -1) first = i; // 记录第一次出现
            last = i; // 不断更新，最后一次留下的就是终点
        }
    }
    
    cout << first << " " << last << endl;
    return 0;
}

版本 2：二分 + 线性探测版 (Hybrid Search)

思路： 先用标准二分找到任意一个等于 target 的位置，然后以该位置为中心，分别向左和向右移动指针，直到遇到不等于 target 的数。

复杂度分析：

• 时间复杂度：平均 $O(\log n)$，但最坏情况（数组里全是 8）会退化到 $O(n)$。
• 空间复杂度：$O(n)$。

/*
 * 优点：比纯暴力快，适合随机分布的数据。
 * 易错点：向左右探测时，注意不要越过数组边界 [0, n-1]。
 */
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, target;
    if (!(cin >> n >> target)) return 0;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    int l = 0, r = n - 1, mid_idx = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) {
            mid_idx = mid;
            break;
        } else if (nums[mid] < target) l = mid + 1;
        else r = mid - 1;
    }

    if (mid_idx == -1) {
        cout << "-1 -1" << endl;
    } else {
        int start = mid_idx, end = mid_idx;
        // 向左线性探测
        while (start > 0 && nums[start - 1] == target) start--;
        // 向右线性探测
        while (end < n - 1 && nums[end + 1] == target) end++;
        cout << start << " " << end << endl;
    }
    return 0;
}

版本 3：最优解 - 纯双二分版 (Optimal Dual Binary Search)

思路： 通过两次独立的二分查找，分别锁定左边界和右边界。

• 找左边界：当 nums[mid] == target 时，不停止，继续向左收缩 (r = mid - 1)。
• 找右边界：当 nums[mid] == target 时，继续向右探测 (l = mid + 1)。

复杂度分析：

• 时间复杂度：$O(\log n)$。严格对数级别，是本题的满分标准。
• 空间复杂度：$O(n)$。

/*
 * 适用场景：n 极大，或题目强制要求 $O(\log n)$。
 * 关键点：mid = l + (r - l) / 2 防止 L+R 溢出。
 * 易错点：二分终止条件是 l <= r，记录 ans 的变量初始值应为 -1。
 */
#include <iostream>
#include <vector>

using namespace std;

// 封装二分逻辑，type=0 找左边界，type=1 找右边界
int findBound(const vector<int>& nums, int target, int type) {
    int n = nums.size();
    int l = 0, r = n - 1, ans = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) {
            ans = mid;
            if (type == 0) r = mid - 1; // 找左边，压缩右边界
            else l = mid + 1;           // 找右边，压缩左边界
        } else if (nums[mid] < target) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false); // 竞赛必备：取消同步流提高 I/O 速度
    cin.tie(0);

    int n, target;
    if (!(cin >> n >> target)) return 0;
    
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    if (n == 0) {
        cout << "-1 -1" << endl;
        return 0;
    }

    int leftIdx = findBound(nums, target, 0);
    int rightIdx = findBound(nums, target, 1);

    cout << leftIdx << " " << rightIdx << endl;
    return 0;
}

时间复杂度优化建议

1. 使用 STL 函数 (进阶技巧)： 在 NOIP 竞赛中，C++ 标准库提供了 std::lower_bound 和 std::upper_bound。

   • lower_bound：返回第一个 大于或等于 target 的迭代器。
   • upper_bound：返回第一个 大于 target 的迭代器。

   优化版代码片段：

   auto it_l = lower_bound(nums.begin(), nums.end(), target);
   if (it_l == nums.end() || *it_l != target) {
       cout << "-1 -1" << endl;
   } else {
       auto it_r = upper_bound(nums.begin(), nums.end(), target);
       // it_r 指向第一个 > target 的位置，所以减 1 才是终点
       cout << (it_l - nums.begin()) << " " << (it_r - nums.begin() - 1) << endl;
   }
   

   这种写法不仅效率极高（底层是高度优化的二分），而且能极大减少考场上手写二分写死循环的风险。

2. 避免频繁的 vector 拷贝： 在函数传递参数时，务必使用 const vector<int>& nums（引用传递），否则每次调用函数都会复制一遍数组，时间复杂度会退化成 $O(n)$。

3. 读入优化： 当 $n \ge 10^5$ 时，cin/cout 必须配合 ios::sync_with_stdio(false); cin.tie(0);，或者改用 scanf/printf。

教练寄语：二分查找虽然简单，但“边界控制”是魔鬼。建议在草稿纸上分别模拟 target 在最左端、最右端、不存在这三种情况，确保你的 while 循环能正确终止。加油！