Editorial for Đếm trong đoạn

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Tiến hành sắp xếp mảng $a$ ~a~ theo thứ tự tăng dần. Với mỗi truy vấn, gọi $i$ ~i~ là chỉ số nhỏ nhất thỏa mãn giá trị phần tử lớn hơn hoặc bằng $l$ ~l~ và $j$ ~j~ là chỉ số lớn nhất thỏa mãn giá trị phần tử nhỏ hơn hoặc bằng $r$ ~r~ (sử dụng Tìm kiếm nhị phân, có thể sử dụng hàm lower_bound và upper_bound). Đáp án của bài toán là số lượng chỉ số nằm trong đoạn $[i,j]$ ~[i,j]~.

Độ phức tạp: $O(n.log(n)+q.log(n))$ ~O(n.log(n)+q.log(n))~.

Editorial for Đếm trong đoạn

Comments