Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Bảng thưa RMQ tìm min đoạn

    Cho mảng tĩnh a0,…,an−1a_0,\dots,a_{n-1}a0​,…,an−1​ (không thay đổi). Trả lời qqq truy vấn l r: giá trị nhỏ nhất trong đoạn [l,r][l, r][l,r] (chỉ số từ 000, bao gồm hai đầu). Dùng bảng thưa (sparse table) để mỗi truy vấn là O(1)O(1)O(1).

    • Định dạng đầu vào:

      Dòng đầu: nnn, qqq. Dòng hai: nnn phần tử. qqq dòng: mỗi dòng lll, rrr.

    • Ràng buộc đầu vào:

      1≤n≤2⋅1051 \le n \le 2\cdot10^51≤n≤2⋅105, 1≤q≤5⋅1051 \le q \le 5\cdot10^51≤q≤5⋅105, ∣ai∣≤109|a_i| \le 10^9∣ai​∣≤109.

    • Định dạng đầu ra:

      Mỗi truy vấn in giá trị nhỏ nhất trên một dòng.

    Ví dụ:

    Đầu vào:

    5 3
4 2 7 1 5
0 4
1 2
3 3

    Đầu ra:

    1
2
1

    Giải thích:

    Min cả mảng = 1. Min[1..2]=min(2,7)=2. Min[3..3]=1.

    Đang tải editor...