DQUERY

DQUERY-spoj
- Tóm tắt : cho n phần tử (n<=30000 ) với mỗi truy vấn (i,j) tìm số lượng phần tử khác nhau trong đoạn [i,j]
- giải : ta xử lí offline truy vấn , xét trong đoạn [i,j] có bao nhiêu phần tử mà ta chỉ lưu 1 vị trí đối với các phần tử = nhau . đầu tiên gom chỉ số của truy vấn và dãy a, sort lại tăng dần :
- Cách 1 : với truy vấn sort theo chỉ số bên phải. Với mỗi truy vấn , tìm trong đoạn [i,j] có bao nhiêu phần tử đã được đánh dấu , ngược lại cập nhật vị trí mới , xóa vị trí cũ
- Cách 2 : với truy vấn sort theo chỉ số bên trái , đầu tiên ta khởi tạo đánh dấu vị trí đầu tiên của tất cả các phần tử khác nhau . với mỗi truy vấn , mỗi lần loại 1 chỉ số ta cập nhập cho thằng sau nó trái nhất. Ứng dụng : BDOI16E-spoj
CODE-theo cách 1