Truy vấn phạm vi mảng: phần tử tần suất bằng giá trị trong C

Cho mảng N phần tử, truy vấn Q(start, end): đếm số giá trị p xuất hiện đúng p lần trong đoạn [start, end].

Ví dụ

Array: {1,5,2,3,1,3,5,7,3,9,8}
Q(1,8): 1 xuất hiện 1 lần, 3 xuất hiện 3 lần -> 2
Q(0,2): 1 xuất hiện 1 lần -> 1

Thuật toán

query(s,e)
    MAP freq
    VỚI i=s ĐẾN e: freq[arr[i]]++
    count = 0
    VỚI (key,val) IN freq
        NẾU key == val -> count++
    TRẢ VỀ count

Chương trình C++ ví dụ

#include <iostream>
#include <map>
using namespace std;

int query(int start, int end, int arr[]) {
    map freq;
    for (int i = start; i <= end; i++) freq[arr[i]]++;
    int count = 0;
    for (auto x : freq) if (x.first == x.second) count++;
    return count;
}

int main() {
    int A[] = {1,5,2,3,1,3,5,7,3,9,8};
    int queries[][2] = {{0,1},{1,8},{0,2},{1,6},{3,5},{7,9}};
    for (int i = 0; i < 6; i++)
        cout << "Query " << i+1 << " = " << query(queries[i][0], queries[i][1], A) << endl;
}

Kết quả

Answer for Query 1 = 1
Answer for Query 2 = 2
Answer for Query 3 = 1
Answer for Query 4 = 1
Answer for Query 5 = 1
Answer for Query 6 = 0