你好！作为金牌教练，我非常理解这种“暴力法竟然没挂”的挫败感。

在现代评测机（如洛谷、Codeforces 或 NOI 专用机）上，单秒处理次数通常在 $2 \times 10^8 \sim 5 \times 10^8$ 之间。我们之前的测试点 $n \cdot m \approx 6.5 \times 10^8$，如果选手的暴力法写得常数极小（比如直接用 for 循环比对），确实有概率“硬压”过去。

为了彻底卡掉 $O(N \cdot M)$，我们需要将运算量级提升至 $10^9$ 以上，同时利用针对性数据（让暴力法每次都扫满全串）来破坏其缓存优化。

优化后的数据生成器 (卡暴力强化版)

强化策略：

1. 量级提升：将 $N$ 提升至 $10^5$，将 $M$ 提升至 $2 \times 10^4$，总运算量 $2 \times 10^9$。
2. 强制全扫描：生成大量“不存在”或“在数组末尾”的查询。暴力法必须扫完整个数组才能得出结论。
3. 文件体积控制：为了保证 $10^5$ 规模下的文件仍在 2MB 左右，我们减小了数值的位数（使用较小的数）。

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

using namespace std;

// ================= 标准答案：二分查找 =================
pair<int, int> solve_query(int n, const vector<int>& a, int k) {
    int first = -1, last = -1;
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= k) {
            if (a[mid] == k) first = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] <= k) {
            if (a[mid] == k) last = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    return {first, last};
}

// ================= 数据生成逻辑 =================
mt19937 rng(time(0));

void generate_test(int id) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";
    ofstream fout(in_name);

    int n, m;
    vector<int> a;
    vector<int> queries;

    if (id <= 2) { // 极小规模
        n = 10; m = 5;
        for(int i=0; i<n; ++i) a.push_back(rng() % 20);
        sort(a.begin(), a.end());
        for(int i=0; i<m; ++i) queries.push_back(rng() % 25);
    } 
    else if (id == 3) { // 全同测试点
        n = 100000; m = 20000;
        a.assign(n, 1);
        for(int i=0; i<m; ++i) queries.push_back(1);
    }
    else { // 核心卡暴力测试点
        // N * M 达到 2 * 10^9，足以卡掉 1s 内的 O(NM)
        n = 100000; 
        m = 20000; 
        
        // 构造一个递增序列
        for(int i=0; i<n; ++i) a.push_back(i); 

        // 构造针对性的 Query
        for(int i=0; i<m; ++i) {
            int coin = rng() % 10;
            if (coin < 4) {
                // 1. 查询不存在的大数 (暴力法必须扫满全串)
                queries.push_back(n + 100 + (rng() % 1000));
            } else if (coin < 8) {
                // 2. 查询数组末尾的数 (暴力法必须扫到最后)
                queries.push_back(n - 1 - (rng() % 10));
            } else {
                // 3. 随机查询
                queries.push_back(rng() % n);
            }
        }
    }

    // 写入输入文件
    fout << n << " " << m << "\n";
    for(int i=0; i<n; ++i) fout << a[i] << (i == n-1 ? "" : " ");
    fout << "\n";
    for(int i=0; i<m; ++i) fout << queries[i] << "\n";
    fout.close();

    // 生成输出文件
    ofstream fans(out_name);
    for(int i=0; i<m; ++i) {
        pair<int, int> res = solve_query(n, a, queries[i]);
        fans << res.first << " " << res.second << "\n";
    }
    fans.close();

    cout << "Test Case " << id << " [N=" << n << ", M=" << m << "] - " << (double)n*m << " ops" << endl;
}

int main() {
    for (int i = 1; i <= 10; ++i) {
        generate_test(i);
    }
    return 0;
}

为什么这组数据能卡掉暴力？

1. 计算总量：
   • 在测试点 4-10 中，$N=10^5, M=2 \times 10^4$，理论计算量为 $2 \times 10^9$。
   • 在 1.0s 的时限下，绝大多数评测机只能跑到 $5 \times 10^8$。$2 \times 10^9$ 会让暴力程序超时 4 倍左右。
2. 破坏“提前退出” (Early Exit)：
   • 很多暴力写法会写 if (a[i] > k) break;。
   • 对策：我生成的 Query 有 40% 是比数组里所有数都大的（n + 100）。这意味着暴力代码必须走完整个 for(i=0; i<n; ++i) 循环才能确定“找不到”，从而彻底废掉 break 的作用。
3. 针对缓存优化 (Cache Friendly)：
   • 如果查询值都在开头，CPU 的一级缓存会起作用。
   • 对策：通过生成大量末尾查询，强制 CPU 进行长距离内存寻址和比对。

文件大小说明

• $N=10^5$ 的数组，数字是 $0, 1, 2...$。
• 每个数字平均 5 字节加空格，共约 $600\text{KB}$。
• $M=2 \times 10^4$ 的查询，每个数字约 5 字节，共约 $120\text{KB}$。
• 单组输入文件约 $0.7\text{MB}$，10 组总计约 7MB（稍微超过了 2MB 理想值，但在现代 OJ 系统中是非常轻量的量级，且能完美区分算法）。

辅导建议

当学生告诉你“我的暴力过了”时，请带他看一眼这个数据生成器中的 $N \cdot M$ 乘积。告诉他：

“在竞赛中，我们默认机器每秒执行 $10^8$ 次运算。如果题目范围给到 $10^5$，而你的算法是 $O(N^2)$，那么出题人只需要把 $M$ 稍微调大一点，你的程序就会瞬间从 0ms 变成 10s。”

这就是二分查找（$O(\log N)$）存在的意义！加油！

你好！作为教练，我将为你展示这道二分查找模板题的进化过程。在 NOI 竞赛中，从暴力思维转向对数复杂度思维是每一个选手的必经之路。

第一阶段：朴素暴力算法 ($O(M \times N)$)

思路思考： 对于每一个询问，我们直接遍历整个数列。第一次遇到 $k$ 时记录起始位置，最后一次遇到 $k$ 时记录终止位置。

#include <iostream>
#include <vector>

using namespace std;

/**
 * 暴力版本：线性扫描
 * 时间复杂度：O(M * N) - 10^4 * 10^5 = 10^9 运算，必 TLE
 * 空间复杂度：O(N) - 存储数组
 */
int main() {
    // 基础优化：流同步加速
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    while (m--) {
        int k;
        cin >> k;
        int first = -1, last = -1;
        
        // 线性扫描
        for (int i = 0; i < n; ++i) {
            if (a[i] == k) {
                if (first == -1) first = i; // 第一次遇到
                last = i; // 每次遇到都更新，最后一次即为终止
            }
        }
        cout << first << " " << last << "\n";
    }

    return 0;
}

第二阶段：标准二分查找 ($O(M \times \log N)$)

思路思考： 既然数组是有序的，我们可以利用二分查找。寻找“第一个等于 $k$ 的数”和“最后一个等于 $k$ 的数”。

#include <cstdio> // 竞赛中常用 scanf/printf 提高 IO 速度

using namespace std;

const int MAXN = 100005;
int a[MAXN];
int n, m;

/**
 * 寻找左边界：第一个 >= k 的位置
 */
int findFirst(int k) {
    int l = 0, r = n - 1;
    int ans = -1;
    while (l <= r) {
        // 关键点：防止 (l+r) 溢出 int 范围
        int mid = l + (r - l) / 2; 
        if (a[mid] >= k) {
            if (a[mid] == k) ans = mid; // 记录当前位置，继续往左找
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

/**
 * 寻找右边界：最后一个 <= k 的位置
 */
int findLast(int k) {
    int l = 0, r = n - 1;
    int ans = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] <= k) {
            if (a[mid] == k) ans = mid; // 记录当前位置，继续往右找
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

int main() {
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

    while (m--) {
        int k;
        scanf("%d", &k);
        // 执行两次二分，复杂度 O(log N)
        printf("%d %d\n", findFirst(k), findLast(k));
    }
    return 0;
}

第三阶段：STL 精简版 ($O(M \times \log N)$)

思路思考： 在 NOI 考场上，为了追求速度，可以直接使用 STL。lower_bound 找第一个 $\ge k$，upper_bound 找第一个 $> k$。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * STL 辅助版本：利用 lower_bound 和 upper_bound
 * 优点：代码极其简短，边界处理极其安全
 */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    while (m--) {
        int k;
        cin >> k;
        
        // it1 指向第一个 >= k 的位置
        auto it1 = lower_bound(a.begin(), a.end(), k);
        
        // 如果 it1 到达结尾或者指向的数不等于 k，说明 k 不存在
        if (it1 == a.end() || *it1 != k) {
            cout << "-1 -1\n";
        } else {
            // it2 指向第一个 > k 的位置，那么 prev(it2) 就是最后一个 k
            auto it2 = upper_bound(a.begin(), a.end(), k);
            // 计算索引位置 (迭代器减法)
            cout << distance(a.begin(), it1) << " " << distance(a.begin(), prev(it2)) << "\n";
        }
    }
    return 0;
}

复杂度分析与演进思考

1. 时间复杂度分析：

   • 暴力版：$O(M \times N)$。在 $N=10^5, M=10^4$ 下，最坏需要 $10^9$ 次运算。NOI 考场机器一秒约处理 $10^8$ 次，故此法会 超时 10 倍以上。
   • 二分版：$O(M \times \log N)$。$\log_2(10^5) \approx 17$。总计算次数约 $10^4 \times 17 \times 2 \approx 3.4 \times 10^5$。远小于时限要求。

2. 空间复杂度分析：

   • 均为 $O(N)$。使用了大小为 $10^5$ 的数组存储数据，占用内存约 $400 \text{ KB}$，远低于 256MB 限制。

关键点与易错点 (教练嘱托)

1. mid 的计算：

   • 易错点：mid = (l + r) / 2。如果 $l$ 和 $r$ 都是 $10^9$ 级，相加会超出 int 范围导致溢出。
   • 对策：写成 mid = l + (r - l) / 2。

2. 死循环风险：

   • 关键点：在更新指针时，一定要 l = mid + 1 或 r = mid - 1。如果写成 l = mid 且 while (l < r)，在 $l$ 和 $r$ 相邻时会因为 mid 向下取整而陷入死循环。

3. 终止条件的判定：

   • 二分查找结束后，并不总是能找到目标。一定要通过 a[ans] == k 或者 if (ans == -1) 来判断该数是否存在。

时间复杂度优化建议

1. IO 优化：在处理 $10^5$ 级数据时，endl 会强制刷新缓冲区，导致输出极慢。请统一使用 "\n"。
2. 预判逻辑：如果 k 比 a[0] 小或比 a[n-1] 大，可以直接输出 -1 -1，省去二分的时间（虽然对量级无影响，但能减小常数）。
3. STL 函数常数：std::lower_bound 是高度优化的，通常比手写的普通二分要快且更安全，推荐在不涉及复杂的二分答案逻辑时优先使用。

希望这些代码和分析能帮你彻底掌握二分查找的精髓！加油！