Truy vấn số phần tử khác nhau trong mảng con trong C++

Trong bài toán này, ta được cho mảng arr[] kích thước n. Và Q truy vấn, mỗi truy vấn gồm hai phần tử l và r. Nhiệm vụ là tạo chương trình giải quyết: truy vấn số phần tử khác nhau trong mảng con trong C++.

Mô tả bài toán

Với mỗi truy vấn, cần tìm tổng số nguyên khác nhau trong mảng con bắt đầu từ arr[l] đến arr[r].

Ví dụ minh họa

Đầu vào

arr[] = {5, 6, 1, 6, 5, 2, 1}
Q = 2
{{1, 4}, {0, 6}}

Đầu ra

3 4

Giải thích

Truy vấn 1: l = 1, r = 4, mảng con[1...4] = {6, 1, 6, 5}, số phần tử khác nhau = 3.

Truy vấn 2: l = 0, r = 6, mảng con[0...6] = {5, 6, 1, 6, 5, 2, 1}, số phần tử khác nhau = 4.

Phương pháp giải

Sử dụng cấu trúc dữ liệu set, độ dài set sẽ cho số phần tử khác nhau của mảng trong khoảng truy vấn. Với mỗi truy vấn, chèn tất cả phần tử trong khoảng vào set. Các phần tử trùng lặp sẽ bị loại, chỉ giữ phần tử khác nhau, do đó kích thước set là kết quả.

Chương trình minh họa:

Ví dụ

#include<bits/stdc++.h>
using namespace std;

int solveQuery(int arr[], int l, int r) {
    set<int> distElements;
    for (int i = (r); i >= (l); i--)
        distElements.insert(arr[i]);
    return distElements.size();
}

int main() {
    int arr[] = {5, 6, 1, 6, 5, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int Q = 2;
    int query[Q][2] = {{1, 4}, {0,6}};
    for(int i = 0; i < Q; i++)
        cout << "For Query " << (i+1) << ": The number of distinct elements in subarray is "
             << solveQuery(arr, query[i][0], query[i][1]) << "\n";
    return 0;
}

Đầu ra

For Query 1: The number of distinct elements in subarray is 3
For Query 2: The number of distinct elements in subarray is 4