Hướng giải: Đếm lớn nhỏ

Tiến hành sắp xếp mảng ~a~ theo thứ tự tăng dần. Với mỗi truy vấn, tìm chỉ số ~i~ nhỏ nhất thỏa mãn giá trị phần tử lớn hơn hoặc bằng ~x~ và chỉ số ~j~ nhỏ nhất thỏa mãn giá trị phần tử lớn hơn ~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~ nằm trong đoạn ~[i,n]~.
• Chỉ số các phần tử lớn hơn ~x~ nằm trong đoạn ~[j,n]~.
• Chỉ số các phần tử nhỏ hơn hoặc bằng ~x~ nằm trong đoạn ~[1,j-1]~.
• Chỉ số các phần tử nhỏ hơn ~x~ nằm trong đoạn ~[1,i-1]~.

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