Nhận xét

• (1): Về miền giá trị của N phần tử trong mảng, chúng ta nhận xét rằng giá trị các phần tử ban đầu giới hạn là 10^9, tuy nhiên ta có thể nén các trị này còn giới hạn 10^5, cụ thể có thể map mỗi giá trị trong mảng A thành N giá trị từ 1..N (do tính chất phân biệt các giá trị trong mảng).
• (2): Do giá trị các phần tử là riêng biệt, với mỗi truy vấn L,R,K, ta giả sử giá trị cần tìm là X, khi đó số lượng phần tử a[i] <= X trong đoạn L..R là K. Ngoài ra nếu K tăng thì giá trị X cũng tăng và ngược lại. Do đó dựa trên tính tuyến tính này, ta có thể sử dụng chặt nhị phân giá trị cần tìm, từ đó đếm xem có bao nhiêu phần tử a[i] <= X trong đoạn L..R.

Lời giải

Dựa trên tính chất (2), ta có thể sử dụng segment tree để lưu trữ các đoạn con đã sort, sử dụng merge sort khi build cây. Cụ thể mỗi node trong cây segment, ta lưu lại mảng của các phần tử của đoạn [l,r] của node đó đã được sort lại.

• Về chi phí lưu trữ: cây có độ cao log(N), mỗi phần tử sẽ xuất hiện ở từng độ cao của cây, do dó chi phí bộ nhớ cho cây segment là O(NlogN). Lưu ý là ta phải dùng vector<> trong C++ để tổ chức mảng sort mỗi node của cây.
• Về chi phí dựng cây: Do mỗi node trên cây khi build là mảng đã sort, do đó node cha được merge từ 2 node con sử dụng merge sort trong O(N). Do đó chi phí build cây là O(NlogN)
• Về chi phí đếm số phần tử a[i] <= X trong đoạn L..R, ta thực hiện đếm trên từng node con, mỗi node con là một mảng đã sort, do đó ta chặt trên từng node con để đếm. Vì thế chi phí tìm kiểm trên đoạn L..R là O((logN)^2) (logN cho duyệt cây, logN cho chặt trên các node con).

Ngoài ra cần lưu ý rằng ta còn một bước là kiểm tra xem phần tử đó có tồn tại trong đoạn L..R hay không.

Nhận xét (1) ban đầu có thể bỏ qua trong bài này.