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

    solution

    Đề bài: [Giải thuật] Đếm số trong khoảng

    Cho một mảng nnn số nguyên đã được sắp xếp không giảm. Có qqq truy vấn, mỗi truy vấn gồm hai số LLL và RRR. Với mỗi truy vấn, hãy đếm xem có bao nhiêu phần tử của mảng nằm trong đoạn [L,R][L, R][L,R] (tính cả hai đầu mút).

    Vì mảng đã được sắp xếp, hãy dùng tìm kiếm nhị phân (lower bound / upper bound) để trả lời mỗi truy vấn nhanh chóng thay vì duyệt toàn bộ mảng.

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

      Dòng đầu chứa hai số nguyên nnn và qqq. Dòng thứ hai chứa nnn số nguyên không giảm. Mỗi dòng trong qqq dòng tiếp theo chứa hai số nguyên LLL và RRR.

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

      1≤n,q≤1051 \le n, q \le 10^51≤n,q≤105; −109≤ai≤109-10^9 \le a_i \le 10^9−109≤ai​≤109; −109≤L≤R≤109-10^9 \le L \le R \le 10^9−109≤L≤R≤109.

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

      Với mỗi truy vấn, in ra trên một dòng số phần tử nằm trong [L,R][L, R][L,R].

    Ví dụ:

    Đầu vào:

    6 3
1 2 2 5 8 10
2 5
0 1
6 9

    Đầu ra:

    3
1
1

    Giải thích:

    Mảng: 1 2 2 5 8 10. [2,5] có {2,2,5}=3 phần tử; [0,1] có {1}=1; [6,9] có {8}=1.

    Đang tải editor...