Editorial for Nhỏ lớn lớn nhỏ

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~. Với mỗi truy vấn, tiến hành tìm chỉ số phần tử nhỏ nhất thỏa mãn lớn hơn hoặc bằng $x$ ~x~ và chỉ số phần tử nhỏ nhất thỏa mãn lớn hơn $x$ ~x~ bằng Tìm kiếm nhị phân (có thể sử dụng hàm lower_bound và upper_bound). Gọi hai chỉ số đó lần lượt là $i$ ~i~ và $j$ ~j~. Khi đó:

Phần tử nhỏ nhất thỏa mãn lớn hơn hoặc bằng $x$ ~x~ là $a_i$ ~a_i~.
Phần tử nhỏ nhất thỏa mãn lớn hơn $x$ ~x~ là $a_j$ ~a_j~.
Phần tử lớn nhất thỏa mãn nhỏ hơn hoặc bằng $x$ ~x~ là $a_{j-1}$ ~a_{j-1}~.
Phần tử lớn nhất thỏa mãn nhỏ hơn $x$ ~x~ là $a_{i-1}$ ~a_{i-1}~.

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

Editorial for Nhỏ lớn lớn nhỏ

Comments