C++ में उपसरणी में विशिष्ट तत्वों की संख्या के लिए क्वेरीज़ | सेट 2

समस्या विवरण

इस समस्या में, हमें आकार n का एक सरणी arr[] दिया गया है और हमें एक क्वेरी दी गई है। प्रत्येक क्वेरी में दो मान (L, R) होते हैं। हमारा कार्य उपसरणी में विशिष्ट तत्वों की संख्या के लिए क्वेरीज़ को हल करने के लिए एक प्रोग्राम बनाना है।

यहां, हमें उन विशिष्ट पूर्णांकों की कुल संख्या ढूंढनी होगी जो इंडेक्स (L-1) से (R-1) तक की उपसरणी में मौजूद हैं।

उदाहरण

इनपुट

arr[] = {4, 6, 1, 3, 1, 6, 5}
query = [1, 4]

आउटपुट

4

व्याख्या

क्वेरी 1 के लिए: L = 1 और R = 4, हमें इंडेक्स 0 से 3 तक विशिष्ट तत्वों की संख्या ढूंढनी है, जो 4 है।

क्वेरी 2 के लिए: L = 2 और R = 6, हमें इंडेक्स 1 से 5 तक विशिष्ट तत्वों की संख्या ढूंढनी है, जो 3 है।

समाधान दृष्टिकोण

प्रत्येक क्वेरी को हल करने का एक सरल दृष्टिकोण सरणी को L से R तक पार करना और तत्वों को सेट में संग्रहीत करना है, जिसका आकार क्वेरी का परिणाम देगा। इसी पर पिछले सेट में चर्चा की गई है।

समस्या को हल करने का एक अधिक प्रभावी तरीका सेगमेंट ट्री (Segment Tree) डेटा संरचना का उपयोग करना है। यह दिए गए रेंज के लिए विशिष्ट तत्वों की संख्या संग्रहीत करेगा।

सेगमेंट ट्री एक विशेष प्रकार का ट्री है, जो जानकारी को खंडों (segments) के रूप में संग्रहीत करता है।

सेगमेंट ट्री का लीफ नोड सरणी के तत्वों को दर्शाता है। और गैर-लीफ नोड्स आवश्यक मान के साथ खंडों को दर्शाते हैं। यहां, यह विशिष्ट तत्वों को संग्रहीत करेगा। इस डेटा संरचना के कार्यान्वयन के लिए, हम सेट (Set) का उपयोग करेंगे।

कार्यक्रम उदाहरण

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

set<int>* segmentTree;

void CreateSegmentTree(int i, int s, int e, int arr[]) {
    if (s == e) {
        segmentTree[i].insert(arr[s]);
        return;
    }
    CreateSegmentTree(2 * i, s, (s + e) / 2, arr);
    CreateSegmentTree(1 + 2 * i, 1 + (s + e) / 2, e, arr);
    segmentTree[i].insert(segmentTree[2 * i].begin(), segmentTree[2 * i].end());
    segmentTree[i].insert(segmentTree[2 * i + 1].begin(), segmentTree[2 * i + 1].end());
}

set<int> findDistSubarray(int node, int l, int r, int a, int b) {
    set<int> left, right, distinctSubarray;
    if (b < l || a > r)
        return distinctSubarray;
    if (a <= l && r <= b)
        return segmentTree[node];
    left = findDistSubarray(2 * node, l, (l + r) / 2, a, b);
    distinctSubarray.insert(left.begin(), left.end());
    right = findDistSubarray(1 + 2 * node, 1 + (l + r) / 2, r, a, b);
    return distinctSubarray;
}

int main() {
    int arr[] = {4, 6, 1, 3, 1, 6, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int query[] = {1, 4};
    int i = (int)ceil(log2(n));
    i = (2 * (pow(2, i))) - 1;
    segmentTree = new set<int>[i];
    CreateSegmentTree(1, 0, n - 1, arr);
    set<int> distCount = findDistSubarray(1, 0, n - 1, (query[0]-1), (query[1]-1));
    cout << "उपसरणी में विशिष्ट तत्वों की संख्या " << distCount.size();
    return 0;
}

आउटपुट

उपसरणी में विशिष्ट तत्वों की संख्या 4