二分查找：把边界一次性钉死

// 有序数组里查找 —— 暴力：从头一个个看过去
//
// 输入：第一行 n q
//       第二行 n 个**从小到大**排好序的整数（可以有重复）
//       接下来 q 行，每行一个 x
// 输出：q 行，每行三个数 L U C
//         L = 第一个 >= x 的位置（都比 x 小就输出 n+1）
//         U = 第一个 >  x 的位置（都不比 x 大就输出 n+1）
//         C = x 在数组里出现了几次
//
// 为什么要同时输出这三个？因为它们正好是二分查找的三种常见需求，
// 而且 C = U - L 这个关系本身就很值得记住 ——
// 「出现了几次」不用另写代码，两个二分一减就出来了。
//
// 这份暴力从头扫到尾，O(n) 一次询问，总共 O(nq)。
// 完全正确，而且**它是那三个定义的最诚实的表述** —— 对拍时拿它当标准答案。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

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

    for (int k = 0; k < q; k++) {
        long long x;
        cin >> x;

        int L = n + 1, U = n + 1;
        for (int i = 1; i <= n; i++) if (a[i] >= x) { L = i; break; }   // 第一个 >= x
        for (int i = 1; i <= n; i++) if (a[i] >  x) { U = i; break; }   // 第一个 >  x

        cout << L << " " << U << " " << (U - L) << "\n";
    }
    return 0;
}

// ⚠ 这是一份**故意写错**的二分 —— 它会死循环
//
// 点「运行 ▶」跑一下，你会看到「超时，被强制结束」。
// 这不是机器慢，是这段代码永远跑不完。
//
// 错在哪：把 l = mid + 1 写成了 l = mid。
//
// 看着好像更保险（「万一 mid 就是答案呢」），实际上是致命的：
//
//   当区间只剩两个数时，比如 l = 3, r = 4：
//       mid = 3 + (4 - 3) / 2 = 3        ← 下取整，mid 等于 l
//   如果这时走 else 分支（l = mid），l 还是 3，r 还是 4，
//   **区间一点都没变**，下一轮算出来的 mid 还是 3……
//
//   于是它就在这里原地打转，直到被判超时。
//
// 记住这个判断方法：
//   **写完二分，拿「区间只剩两个数」这种最小情况代进去走一遍。**
//   只要有一个分支让区间没缩小，就是死循环。
//
// 想验证「另一种写法」也一样：把 mid 改成上取整
//     int mid = l + (r - l + 1) / 2;
// 配 l = mid 就是对的，配 r = mid 又会死循环。
// 所以 **mid 的取整方向和分支的写法必须配套**，不能混搭。

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 一个写死的小例子，不用输入
    vector<long long> a = {0, 1, 3, 3, 5, 7};    // a[1..5]，1 基
    int n = 5;
    long long x = 4;                              // 找第一个 >= 4 的位置（正确答案是 5）

    cout << "在 1 3 3 5 7 里找第一个 >= 4 的位置（正确答案：5）\n";
    cout << "如果这段输出停住了，就是死循环了 —— 等它超时被掐断。\n\n";

    int l = 1, r = n + 1;
    long long step = 0;
    while (l < r) {
        int mid = l + (r - l) / 2;
        step++;

        // 只打印前几轮 —— 后面全都一模一样，打出来只会刷屏
        if (step <= 8) {
            cout << "第 " << step << " 轮：l = " << l << ", r = " << r << ", mid = " << mid << "\n";
        } else if (step == 9) {
            cout << "……从这里开始，每一轮的 l、r、mid 都和上一轮完全相同。\n";
            cout << "区间不再缩小，循环永远不会结束。等它超时吧。\n";
        }
        cout.flush();

        if (a[mid] >= x) r = mid;
        else l = mid;                             // ← 错！这里必须是 mid + 1
    }

    cout << "答案 = " << l << "\n";
    return 0;
}

// 有序数组里查找 —— 二分
//
// 输入输出和 brute.cpp 完全一样。一次询问只要 O(log n)。
//
// ============ 这一章只需要背这一个模板 ============
//
//   int l = 1, r = n + 1;          // 答案的候选范围是 [l, r]，r 多留一格表示「找不到」
//   while (l < r) {
//       int mid = l + (r - l) / 2;
//       if (check(mid)) r = mid;   // mid 满足条件 → 答案在 [l, mid]，mid 自己也可能是答案
//       else l = mid + 1;          // mid 不满足   → 答案在 [mid+1, r]
//   }
//   // 出来时 l == r，就是答案
//
// 三个要点，缺一个就会出事：
//
//   1. **循环条件是 l < r，不是 l <= r。** 相等时区间只剩一个数，已经是答案了，
//      再进循环就可能原地打转。
//
//   2. **两个分支必须是 r = mid 和 l = mid + 1。**
//      注意不对称：一边是 mid，另一边是 mid+1。
//      因为 mid 是**下取整**的，如果写成 l = mid，当 l 和 r 只差 1 时 mid 就等于 l，
//      区间一点都没缩小 —— 死循环。（deadloop.cpp 就是这么写的，可以去跑一下。）
//
//   3. **mid 要写成 l + (r - l) / 2，不要写 (l + r) / 2。**
//      后者在 l、r 都接近 int 上限时会溢出成负数。本题不会，但养成习惯。
//
// 剩下的全部变化，都只是换那个 check：
//     找第一个 >= x  →  check(mid) 是 a[mid] >= x
//     找第一个 >  x  →  check(mid) 是 a[mid] >  x
//
// **不要去记「找左边界要不要 +1」这种口诀。** 记住上面这个模板，
// 然后每次只问自己一句：「mid 满足条件时，答案还可能在 mid 右边吗？」
//   不可能 → r = mid（把 mid 留着）
//   可能   → l = mid + 1（把 mid 扔掉）

#include <bits/stdc++.h>
using namespace std;

int n;
vector<long long> a;

/** 第一个 >= x 的位置，没有就返回 n+1 */
int lowerPos(long long x) {
    int l = 1, r = n + 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) r = mid;      // mid 够大了，答案在 mid 或它左边
        else l = mid + 1;              // mid 太小，答案只能在右边
    }
    return l;
}

/** 第一个 > x 的位置，没有就返回 n+1 */
int upperPos(long long x) {
    int l = 1, r = n + 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] > x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> n >> q)) return 0;

    a.assign(n + 2, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int k = 0; k < q; k++) {
        long long x;
        cin >> x;
        int L = lowerPos(x), U = upperPos(x);
        cout << L << " " << U << " " << (U - L) << "\n";
    }
    return 0;
}

// 有序数组里查找 —— 直接用 STL
//
// 输入输出和 brute.cpp、fast.cpp 完全一样。
//
// C++ 标准库早就把这两个二分写好了：
//     lower_bound(first, last, x)   第一个 >= x 的位置
//     upper_bound(first, last, x)   第一个 >  x 的位置
// 它们返回的是**迭代器**，减去起始迭代器就得到下标。
//
// 比赛里能用就用它 —— 少写十行就少十个出错的地方。
//
// 但请注意两件事：
//   1. **必须先排好序**，否则结果是未定义的（不会报错，只会给你一个错答案）。
//   2. **对 vector / 数组用没问题，对 set / map 千万别用**：
//      那些容器不是连续存储的，标准库的 lower_bound 在上面会退化成 O(n)。
//      set 自己带成员函数 s.lower_bound(x)，用那个。
//
// 那为什么还要手写一遍（fast.cpp）？
//   因为第 9 章的「二分答案」根本没有数组可以给 lower_bound 用 ——
//   那里二分的是「答案本身」，check 是一个自己写的函数。
//   手写模板必须刻进肌肉记忆，STL 只是顺手的时候用。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];        // 这里用 0 基，方便和迭代器换算

    for (int k = 0; k < q; k++) {
        long long x;
        cin >> x;

        // 迭代器 - begin() 得到 0 基下标，+1 换成题目要求的 1 基
        int L = (int)(lower_bound(a.begin(), a.end(), x) - a.begin()) + 1;
        int U = (int)(upper_bound(a.begin(), a.end(), x) - a.begin()) + 1;

        cout << L << " " << U << " " << (U - L) << "\n";
    }
    return 0;
}

// 二分 —— 把每一轮区间怎么收缩打印出来
//
// 输入：n q / n 个升序整数 / q 行 x（用小数据）
// 输出：每次二分的 l、mid、r，以及区间是怎么减半的
//
// 跑一遍，数一下轮数：n = 16 时最多 5 轮，n = 1000 时最多 10 轮，
// n = 10⁹ 时也只要 30 轮。这就是 log 的威力 ——
// **数据规模翻十亿倍，工作量只涨 30 倍。**
//
// 另外注意每一轮的区间长度：16 → 8 → 4 → 2 → 1，一次砍一半，一次都没有例外。
// 如果你的二分某一轮区间没变小，那就是死循环（去看 deadloop.cpp）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    if (!(cin >> n >> q)) return 0;
    if (n <= 0 || n > 40) { cout << "这份是用来看过程的，请用 1 <= n <= 40\n"; return 0; }

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

    cout << "数组：";
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    cout << "\n";

    for (int k = 0; k < q; k++) {
        long long x;
        if (!(cin >> x)) break;

        cout << "\n找第一个 >= " << x << " 的位置：\n";
        int l = 1, r = n + 1, step = 0;
        while (l < r) {
            int mid = l + (r - l) / 2;
            cout << "  第 " << ++step << " 轮：区间 [" << l << ", " << r << "]（还剩 " << (r - l + 1)
                 << " 个候选），mid = " << mid << "，a[" << mid << "] = "
                 << (mid <= n ? to_string(a[mid]) : string("（越界，视为 +∞）"));

            if (mid <= n && a[mid] >= x) {
                cout << " >= " << x << " → 答案在 mid 或左边，r = mid\n";
                r = mid;
            } else if (mid <= n) {
                cout << " < " << x << " → 答案在 mid 右边，l = mid + 1\n";
                l = mid + 1;
            } else {
                cout << " → r = mid\n";
                r = mid;
            }
        }
        cout << "  收敛到 l = r = " << l;
        if (l == n + 1) cout << "（数组里所有数都比 " << x << " 小，没有答案）\n";
        else cout << "，a[" << l << "] = " << a[l] << "\n";
        cout << "  一共 " << step << " 轮（n = " << n << "，理论上限约 log2(" << (n + 1) << ") ≈ "
             << (int)ceil(log2((double)(n + 1))) << " 轮）\n";
    }
    return 0;
}

// 有序数组里查找 —— 二分
//
// 输入输出和 brute.cpp 完全一样。一次询问只要 O(log n)。
//
// ============ 这一章只需要背这一个模板 ============
//
//   int l = 1, r = n + 1;          // 答案的候选范围是 [l, r]，r 多留一格表示「找不到」
//   while (l < r) {
//       int mid = l + (r - l) / 2;
//       if (check(mid)) r = mid;   // mid 满足条件 → 答案在 [l, mid]，mid 自己也可能是答案
//       else l = mid + 1;          // mid 不满足   → 答案在 [mid+1, r]
//   }
//   // 出来时 l == r，就是答案
//
// 三个要点，缺一个就会出事：
//
//   1. **循环条件是 l < r，不是 l <= r。** 相等时区间只剩一个数，已经是答案了，
//      再进循环就可能原地打转。
//
//   2. **两个分支必须是 r = mid 和 l = mid + 1。**
//      注意不对称：一边是 mid，另一边是 mid+1。
//      因为 mid 是**下取整**的，如果写成 l = mid，当 l 和 r 只差 1 时 mid 就等于 l，
//      区间一点都没缩小 —— 死循环。（deadloop.cpp 就是这么写的，可以去跑一下。）
//
//   3. **mid 要写成 l + (r - l) / 2，不要写 (l + r) / 2。**
//      后者在 l、r 都接近 int 上限时会溢出成负数。本题不会，但养成习惯。
//
// 剩下的全部变化，都只是换那个 check：
//     找第一个 >= x  →  check(mid) 是 a[mid] >= x
//     找第一个 >  x  →  check(mid) 是 a[mid] >  x
//
// **不要去记「找左边界要不要 +1」这种口诀。** 记住上面这个模板，
// 然后每次只问自己一句：「mid 满足条件时，答案还可能在 mid 右边吗？」
//   不可能 → r = mid（把 mid 留着）
//   可能   → l = mid + 1（把 mid 扔掉）

#include <bits/stdc++.h>
using namespace std;

int n;
vector<long long> a;

/** 第一个 >= x 的位置，没有就返回 n+1 */
int lowerPos(long long x) {
    int l = 1, r = n + 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) r = mid;      // mid 够大了，答案在 mid 或它左边
        else l = mid + 1;              // mid 太小，答案只能在右边
    }
    return l;
}

/** 第一个 > x 的位置，没有就返回 n+1 */
int upperPos(long long x) {
    int l = 1, r = n + 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] > x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> n >> q)) return 0;

    a.assign(n + 2, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int k = 0; k < q; k++) {
        long long x;
        cin >> x;
        int L = lowerPos(x), U = upperPos(x);
        cout << L << " " << U << " " << (U - L) << "\n";
    }
    return 0;
}