इस समस्या में, हमें आकार N की एक सरणी res[] दी गई है। हमारा कार्य रेंज सम क्वेरी के बाद दी गई सरणी से प्रारंभिक सरणी ज्ञात करना है।
हमें प्रारंभिक सरणी ढूंढनी है जो [s, e, val] क्वेरी करने पर सरणी rel[] लौटाएगी।
प्रत्येक [s, e, val] क्वेरी को इस तरह हल किया जाता है
s -> शुरुआती इंडेक्स
e -> अंतिम इंडेक्स
val -> सरणी में s से e तक प्रत्येक तत्व में जोड़ा जाने वाला अद्यतन मान।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट : rel[] = {7, 4, 8} Query[][] = {{1, 2, 1}, {0, 1, 3}} आउटपुट : {4, 0, 7} व्याख्या −
initialArray = {4, 0, 7}; query = {1, 2, 1}; finalArray = {4, 1, 8} initialArray = {4, 1, 8}; query = {0, 1, 3}; finalArray = {7, 4, 8} समाधान दृष्टिकोण
समस्या का एक सरल समाधान सभी क्वेरी को पार करना है, सभी क्वेरी को हल करें जैसे हम इसे हल करते हैं, फिर अंत में मिली सरणी लौटाएं। यहां, प्रारंभिक सरणी ढूंढने के लिए, हमें इसे विपरीत तरीके से संचालित करने की आवश्यकता है, यानी दी गई सरणी से घटाएं।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <iostream> using namespace std; void calcInitialArrayQueries(int arr[], int n, int query[][3], int q) { for (int i = 0; i < q; i++) { for (int j = query[i][0];j <= query[i][1]; j++) { arr[j] = arr[j] - query[i][2]; } } for (int i = 0; i < n; i++) cout<<arr[i]<<" "; } int main() { int arr[] = { 5, 1, 8, 2, 9}; int n = sizeof(arr) / sizeof(arr[0]); int query[][3] = { {0, 2, -2}, {1, 4, 3}}; int q = sizeof(query) / sizeof(query[0]); cout<<"प्रारंभिक सरणी : "; calcInitialArrayQueries(arr, n, query, q); return 0; } आउटपुट
प्रारंभिक सरणी : 7 0 7 -1 6
