Bài này phải xử lí offline. Tức là đọc hết tất cả q truy vấn.

Ta sẽ kết hợp giữa n phần tử của dãy ban đầu với q truy vấn vào một mảng , sort lại để xử lí

Mỗi phần tử trong mảng này cần lưu lại

• các chỉ số i,j, với dãy thì i=j còn với truy vấn thì như đề
• giá trị k của dãy là giá trị của mảng còn truy vấn thì như đề
• type là loại của phần tử này, type = -1 là dãy, type = 0 là truy vấn
• id là chỉ số của truy vấn

Thêm một mảng res[q] để cập nhật nghiệm của các truy vấn

Bài này ta sẽ sort lại theo giá trị để BIT. sort giảm dần theo giá trị để mỗi lần đi đến phần tử i thì ta chỉ xét nó là dãy hay truy vấn.

Nếu là dãy thì cập nhật vị trí của nó, tất cả những chỉ số sau nó và bằng nó đều thừa nhận giá trị này lớn hơn do ta đã sort giảm dần (tức là những thằng phía sau nó đảm bảo không lớn hơn số này)

Còn nếu là truy vấn thì : thứ nhất ta đã đảm bảo đi qua mọi phần tử lớn hơn nó rồi do sort giảm nên ta chỉ việc đếm thôi. Đếm bằng BIT trên đoạn i..j.

Chú ý một điều là do các phần tử lớn hơn k nên những phần tử bằng nhau phải bỏ qua. Để xử lí điều này, trong lúc sort ta đẩy những thằng trong dãy ra sau những truy vấn nếu chúng có cùng giá trị , tức là lúc ta đi qua các phần tử này thì:

• những thằng trong dãy thì chưa đi qua những thằng <= nó
• những thằng trong truy vấn thì đảm bảo không được cập nhật trước khi qua những thằng bằng nó