Editorial for Đếm 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~ theo thứ tự tăng dần. Với mỗi truy vấn, tìm chỉ số $i$ ~i~ nhỏ nhất thỏa mãn giá trị phần tử lớn hơn hoặc bằng $x$ ~x~ và chỉ số $j$ ~j~ nhỏ nhất thỏa mãn giá trị phần tử lớn hơn $x$ ~x~ bằng Tìm kiếm nhị phân. Khi đó:

Chỉ số các phần tử lớn hơn hoặc bằng $x$ ~x~ nằm trong đoạn $[i,n]$ ~[i,n]~.
Chỉ số các phần tử lớn hơn $x$ ~x~ nằm trong đoạn $[j,n]$ ~[j,n]~.
Chỉ số các phần tử nhỏ hơn hoặc bằng $x$ ~x~ nằm trong đoạn $[1,j-1]$ ~[1,j-1]~.
Chỉ số các phần tử nhỏ hơn $x$ ~x~ nằm trong đoạn $[1,i-1]$ ~[1,i-1]~.

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

Editorial for Đếm lớn nhỏ

Comments