VOJ - DQUERY

Source: DQUERY
Tags: Data Structures

Problem:
Cho một dãy số N phần tử và các truy vấn-d. Một truy vấn-d là một cặp (i, j), với mỗi truy vấn-d bạn cần trả về số lượng giá trị phân biệt trong dãy con A[i], A[i + 1], ..., A[j].
1 ≤ N ≤ 3e4.
1 ≤ A[i] ≤ 1e6.
1 ≤ Q ≤ 2e5.
1 ≤ i ≤ j ≤ N.

Ví dụ:
Input:
5
1 1 2 1 3
3
1 5
2 4
3 5

Output:
3
2
3

Explanation:
(1, 5) → [1, 1, 2, 1, 3] có 3 giá trị phân biệt là 1, 2, 3.
(2, 4) → [1, 2, 1] có 2 giá trị phân biệt là 1, 2.
(3, 5) → [2, 1, 3] có 3 giá trị phân biệt là 1, 2, 3.

Solution:

Ở bài này, ta sẽ xử lý offline các truy vấn.

Gọi BIT[i] là số lượng các giá trị phân biệt trong khoảng từ 1 → i. Tại mỗi vị trí i, nếu giá trị tại vị trí này đã xuất hiện trước đó, ta sẽ loại bỏ nó ra khỏi BIT và cập nhật lại vị trí mới cho nó, push lại vị trí mới này vào cây BIT.

Sau đó, với mỗi truy vấn (a, b) có b = i, ta tính được kết quả: BIT[b] - BIT[a - 1].

Code:

#include <iostream>

#include <algorithm>

using namespace std;

int n, a[30015], q, x[200015], y[200015], id[200015], prev_[1000015], BIT[30015], ans[200015];

bool cmp(int i, int j) {

    return y[i] < y[j];

}

void pop(int x) {

    for (; x <= n; x += x & -x)

        --BIT[x];

}

void push(int x) {

    for (; x <= n; x += x & -x)

        ++BIT[x];

}

int get(int x) {

    int res = 0;

    for (; x; x -= x & -x)

        res += BIT[x];

    return res;

}

int main() {

    cin >> n;

    for (int i = 1; i <= n; i++)

        cin >> a[i];

    cin >> q;

    for (int i = 0; i < q; i++)

        cin >> x[i] >> y[i],

        id[i] = i;

    sort(id, id + q, cmp);

    for (int i = 0, j = 0; j < q; j++) {

        while (i < y[id[j]]) {

            ++i;

            if (prev_[a[i]])

                pop(prev_[a[i]]);

            prev_[a[i]] = i;

            push(i);

        }

        ans[id[j]] = get(y[id[j]]) - get(x[id[j]] - 1);

    }

    for (int i = 0; i < q; i++)

        cout << ans[i] << '\n';

}