इस समस्या में, हमें एक संख्या N दी गई है जो सभी शून्यों से बनी एक सरणी का आकार है और Q क्वेरीज़ जिनमें से प्रत्येक निम्न प्रकार की है -
update(s, e, val) -> यह क्वेरी s से e (दोनों समावेशी) तक के सभी तत्वों को val पर अपडेट करेगी।
हमारा कार्य दिए गए ऑपरेशन को q बार लागू करने के बाद सरणी में विभिन्न संख्याओं की संख्या ज्ञात करना है।
उदाहरण से समझते हैं:
इनपुट: N = 6, Q = 2 Q1 = update(1, 4, 3) Q2 = update(0, 2, 4) आउटपुट: 2
व्याख्या
प्रारंभिक सरणी, arr[] = {0, 0, 0, 0, 0, 0}
क्वेरी 1 - update(1, 4, 3) -> arr[] = {0, 3, 3, 3, 3, 0}
क्वेरी 2 - update(0, 2, 4) -> arr[] = {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
