Tóm tắt đề bài

Có \(N\) cây cột với chiều cao \(h_i\). Ếch chọn xuất phát ở cột \(x\), và luôn nhảy sang phải đến cột gần nhất có chiều cao lớn hơn cột hiện tại (tức là tìm chỉ số nhỏ nhất \(y>x\) sao cho \(h_y>h_x\)). Khi không còn cột như vậy thì dừng.

Với \(Q\) truy vấn, mỗi truy vấn cho biết cột xuất phát \(x_i\), hãy trả lời số bước nhảy tối đa ếch thực hiện được.

Phân tích

• \(N,Q \le 10^5\), nên không thể mô phỏng từng truy vấn theo kiểu “nhảy từng bước” vì có thể thành \(O(NQ)\).
• Bản chất mỗi lần nhảy từ cột \(i\) là sang phần tử lớn hơn gần nhất bên phải (Next Greater Element to the right).

• Nếu ta biết với mỗi \(i\) cột tiếp theo sẽ nhảy đến là \(nxt(i)\), thì đường đi là:

  • \(i \to nxt(i) \to nxt(nxt(i)) \to \dots\)

và số bước nhảy là độ dài chuỗi trên trừ \(1\).

Nhận xét quan trọng (đúng với code AC)

Nếu ta duyệt từ phải sang trái và duy trì một stack các chỉ số có chiều cao tăng dần từ đỉnh xuống (tức là trên đỉnh là phần tử nhỏ nhất), sau khi loại bỏ các phần tử \(\le h_i\), thì:

• stk.top() chính là vị trí cột gần nhất bên phải có chiều cao \(>h_i\).
• Nếu ta đẩy thêm một cột “lính canh” ở vị trí \(n\) với \(h_n\) cực lớn, thì mọi \(i\) luôn tìm được điểm dừng cuối (đi đến cột lính canh).
  Khi đó, số lần nhảy từ \(i\) sẽ bằng: số cột trong stack sau khi pop (bao gồm lính canh và các “đỉnh” lớn dần) trừ \(1\).

Trực giác: các cột còn lại trên stack tạo thành một dãy “kỷ lục” tăng dần khi đi sang phải mà ếch sẽ lần lượt nhảy tới.

Hướng giải quyết

Ý tưởng

Tiền xử lý mảng \(f[i]\) = số lần nhảy nếu bắt đầu từ cột \(i\).

Duyệt \(i\) từ \(N-1\) về \(0\) và dùng stack lưu chỉ số các cột “ứng viên” bên phải:

• Trước khi xử lý, stack chứa một dãy chỉ số tăng dần (theo vị trí) và chiều cao tương ứng tăng dần khi đi từ đỉnh xuống.
• Với cột \(i\), ta loại bỏ tất cả cột ở bên phải có chiều cao \(\le h_i\) vì ếch không thể nhảy tới chúng (và chúng cũng không giúp ích cho các cột bên trái).
• Lúc này đỉnh stack là cột gần nhất bên phải có chiều cao \(> h_i\) (chính là bước nhảy đầu tiên).

• Code AC gán:

  • f[i] = stk.size(); (kích thước stack sau khi pop)
  • Sau đó stk.push(i).

Vì có lính canh ở cuối, f[i] - 1 chính là số bước nhảy từ cột \(i\) (trừ đi cột lính canh).

Thuật toán

1. Đọc \(N,Q\) và mảng \(h[0..N-1]\).
2. Đặt \(h[N] = 10^9 + 7\) (lính canh lớn hơn mọi \(h_i\)).
3. Khởi tạo stack stk và đẩy chỉ số \(N\) vào stack.
4. Duyệt \(i\) từ \(N-1\) xuống \(0\):
   • Trong khi \(h[i] \ge h[stk.top()]\) thì pop.
   • Gán f[i] = stk.size().
   • push(i).
5. Với mỗi truy vấn \(x\) (1-indexed):
   • Đổi sang \(0\)-indexed: \(x \leftarrow x-1\).
   • In ra f[x] - 1.

Vì sao f[i] - 1 là số bước nhảy?

• Stack tại thời điểm xử lý \(i\) (sau khi pop) chứa các “điểm đến” mà ếch sẽ lần lượt nhảy qua nếu xuất phát từ \(i\), theo thứ tự từ gần đến xa, và cuối cùng là cột lính canh.
• Kích thước stack = số cột trong hành trình tính cả lính canh.
• Số bước nhảy = số cạnh = số đỉnh trên đường đi trừ \(1\) \(\Rightarrow\) stk.size() - 1.

Lỗi thường gặp

• Quên xét điều kiện “gần nhất” (nhưng NGE đảm bảo điều này).
• Dùng điều kiện pop sai: phải pop khi \(h[i] \ge h[stk.top()]\) để đảm bảo đỉnh còn lại có chiều cao строго lớn hơn.
• Không có lính canh thì một số vị trí không có NGE, cần xử lý riêng; code AC tránh điều này bằng cách thêm cột \(N\) rất cao.

Độ phức tạp

• Thời gian: \(O(N+Q)\)
  • Mỗi chỉ số được push/pop tối đa 1 lần trên stack.
• Bộ nhớ: \(O(N)\) cho mảng và stack.

Code tham khảo

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

const int MXN = 1e5 + 10;

int h[MXN], f[MXN];

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

    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> h[i];

    // Cột lính canh: cao hơn tất cả để đảm bảo luôn có "điểm dừng"
    h[n] = 1000000007;

    stack<int> stk;
    stk.push(n); // bắt đầu với lính canh

    // Duyệt từ phải sang trái để tìm "next greater" và đồng thời suy ra số bước nhảy
    for (int i = n - 1; i >= 0; i--) {
        while (h[i] >= h[stk.top()]) stk.pop();
        // stk hiện chứa các cột ếch sẽ lần lượt nhảy tới (bao gồm lính canh)
        f[i] = (int)stk.size();
        stk.push(i);
    }

    while (q--) {
        int x;
        cin >> x;
        x--; // 0-indexed
        cout << f[x] - 1 << '\n'; // trừ 1 vì không tính bước vào lính canh như một cột thật
    }
    return 0;
}