DQUERY - D-query - Solution for SPOJ

Problem

https://vn.spoj.com/problems/DQUERY

https://oj.vnoi.info/problem/DQUERY

Truy vấn-d

Cho một dãy số n phần tử a1, a2, …, an và một số các truy vấn-d. Một truy vấn-d là một cặp (i, j) (1 ≤ i ≤ j ≤ n). Với mỗi truy vấn-d (i, j), bạn cần trả về số phần tử phân biệt nằm trong dãy con ai, ai+1, …, aj.

Dữ liệu

Dòng 1: n (1 ≤ n ≤ 30000).
Dòng 2: n số a1, a2, …, an (1 ≤ ai ≤ 10^6).
Dòng 3: q (1 ≤ q ≤ 200000), số lượng truy vấn- d.
Trong q dòng sau, mỗi dòng chứa 2 số i, j biểu thị một truy vấn-d (1 ≤ i ≤ j ≤ n).

Kết quả

Với mỗi truy vấn-d (i, j), in ra số phần tử phân biệt thuộc dãy con ai, ai+1, …, aj trên một dòng.

Ví dụ

Input
5
1 1 2 1 3
3
1 5
2 4
3 5

Output
3
2
3 

Tutorial

Với một truy vấn trên đoạn a..b ta phải đếm số lượng các số có vị trí tận cùng trong đoạn 1..b không nhỏ hơn a.

Dùng BIT bằng cách xử lí offline. Xử lí giống như bài KQUERY

Chèn mảng với truy vấn vào một list với :

Mảng thì a[i].i là giá trị còn a[i].j là vị trí, a[i].type là phân loại là mảng
Truy vấn a[i].i và a[i].j là đoạn còn a[i].id là chỉ số truy vấn Cây BIT lúc này với bit[x] sẽ lưu lại số lượng các vị trí tận cùng của các giá trị khác nhau trong đoạn 1..x

Ta sort tăng dần theo chỉ số j, mỗi lần xét đến một dữ liệu nào đó nếu nó là :

Mảng thì ta sẽ cập nhật. Trước hết là những phần tử có vị trí lớn hơn (tức là đoạn từ i..n) sẽ tăng lên. Sau đó kiểm tra xem trước đó có phần tử nào giống nó không , có thì xóa bỏ nó. Cuối cùng là cập nhật lại vị trí cuối cùng của phần tử đó
Truy vấn thì sẽ lấy nghiệm cho truy vấn. Nghiệm sẽ là số lượng các vị trí tận cùng có gt khác nhau trong đoạn 1..j trừ đi lượng trong đoạn 1..(i-1).

Submission

DQUERY.cpp

Tutorial SPOJ

DQUERY - D-query