C++ में दिए गए ऑपरेशन को q बार लागू करने के बाद सरणी में विभिन्न संख्याओं की संख्या ज्ञात कीजिए

इस समस्या में, हमें एक संख्या N दी जाती है जो एक सरणी के आकार की होती है जिसमें सभी शून्य और Q निम्न प्रकार के प्रत्येक प्रश्न होते हैं -

अपडेट (एस, ई, वैल) -> यह क्वेरी एस से ई (दोनों समावेशी) से वैल तक सभी तत्वों को अपडेट कर देगी।

हमारा कार्य दिए गए ऑपरेशन q बार लागू करने के बाद सरणी में विभिन्न संख्याओं की संख्या ज्ञात करना है

समस्या को समझने के लिए एक उदाहरण लेते हैं,

Input : N = 6, Q = 2
Q1 = update(1, 4, 3)
Q2 = update(0, 2, 4)

Output : 2

स्पष्टीकरण

प्रारंभिक सरणी, एआर [] ={0, 0, 0, 0, 0, 0}

क्वेरी 1 - अपडेट(1, 4, 3) -> arr[] ={0, 3, 3, 3, 3, 0}

प्रश्न 2 - अद्यतन(0, 2, 4) -> गिरफ्तार [] ={4, 4, 4, 3, 3, 0}

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

समस्या का एक सरल समाधान सरणी पर प्रत्येक क्वेरी को निष्पादित करना और फिर सरणी में अद्वितीय मानों की संख्या की गणना करना और एक अतिरिक्त सरणी का उपयोग करना है। और फिर अद्वितीय सरणी की गिनती लौटाएं।

यह समाधान अच्छा है लेकिन समस्या का अधिक कुशल समाधान आलसी प्रसार की अवधारणा का उपयोग करना है। क्वेरी में किए गए रेंज ऑपरेशन को अनुकूलित करने के लिए। हम सरणी में अद्वितीय संख्याओं की संख्या का पता लगाने के लिए क्वेरी ऑपरेशन के लिए आलसी प्रसार कॉल का उपयोग करेंगे। इसके लिए हम एक सेगमेंट ट्री लेंगे और ऑपरेशन निष्पादित होने पर नोड्स को अपडेट करेंगे और ट्री को 0 से इनिशियलाइज़ करेंगे, ऑपरेशन पर अपडेट होने वाले मान वांछित मान लौटाते हैं। यहां वह कार्यक्रम है जो समाधान को बेहतर ढंग से विस्तृत करेगा।

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम

#include <bits/stdc++.h>
using namespace std;
#define N 100005
int lazyST[4 * N];
set<int> diffNo;
void update(int s, int e, int val, int idx, int l, int r){
   if (s >= r or l >= e)
      return;
   if (s <= l && r <= e) {
      lazyST[idx] = val;
      return;
   }
   int mid = (l + r) / 2;
   if (lazyST[idx])
      lazyST[2 * idx] = lazyST[2 * idx + 1] = lazyST[idx];
   lazyST[idx] = 0;
   update(s, e, val, 2 * idx, l, mid);
   update(s, e, val, 2 * idx + 1, mid, r);
}
void query(int idx, int l, int r){
   if (lazyST[idx]) {
      diffNo.insert(lazyST[idx]);
      return;
   }
   if (r - l < 2)
      return;
   int mid = (l + r) / 2;
   query(2 * idx, l, mid);
   query(2 * idx + 1, mid, r);
}
int main() {
   int n = 6, q = 3;
   update(1, 3, 5, 1, 0, n);
   update(4, 5, 1, 1, 0, n);
   update(0, 2, 9, 1, 0, n);
   query(1, 0, n);
   cout<<"The number of different numbers in the array after operation is "<<diffNo.size();
   return 0;
}

आउटपुट

The number of different numbers in the array after operation is 3