用于乘法，替換和乘積的數組查詢 · GeeksForGeeks 中文系列教程

# 用于乘法，替換和乘積的數組查詢 > 原文： [https://www.geeksforgeeks.org/array-queries-for-multiply-replacements-and-product/](https://www.geeksforgeeks.org/array-queries-for-multiply-replacements-and-product/) 這是我們提供的范圍查詢問題，數組大小為 N。給定 3 種查詢類型，您必須回答 M 個指定的查詢。 **類型 1 查詢**：您將獲得 3 個 L L X 形式的值，在這種類型的查詢中，必須將 x 乘以 L 到 R 范圍內的數組元素。 **類型 2 查詢**：在此查詢中，您還將獲得 3 個 LRY 形式的值，執行此類型的查詢后，您將以第一個元素替換為 Y 的形式替換數組元素，第二個元素替換為 2 * Y，并在 L 到 R 范圍內（包括以下內容）替換。 **類型 3 查詢**：在此您將獲得 2 個值 L 和 R，在此您必須查找該范圍內所有數字的乘積。由于此數字可能非常大，因此您必須找到以十進制表示法表示的該數字的尾隨零。例子： ``` Input : arr[] = {2, 4, 3, 5, 5| queries[] = {{3 2 4}, {3 2 5}, {2 2 4 1}, {1 3 3 10}, {3 1 5}} Output : 5 Explanation : Since the first query is of type 3 so we multiply the elements 4 * 3 * 5 = 60. Since the second query is of type 3 so we multiply the elements 4 * 3 * 5 * 5 = 300. Since the third query is of type 2 and the value of Y is 1 so after execution of this query the array becomes [2, 1, 2, 3, 5]. Since the fourth query is of type 1 and the value of x is 10 so after execution of this query the array becomes [2, 1, 20, 3, 5]. Now the last query is of type 3 then we simply multiply all the elements inclusive in the given range i.e. 2 * 1 * 20 * 3 * 5 = 600. Now our task is to calculate the trailing zeros obtained in the type 3 query i.e. 60 has 1 trailing zero, 300 has 2 trailing zeros and 600 has 2 trailing zeros so the answer of this given input is 5. ``` **方法 1**：在此，我們可以簡單地應用暴力方法。在暴力方法中，我們將所有操作應用于數組元素，對于每個類型 3 查詢，我們會將獲得的結果存儲在新數組中，然后針對由此獲得的每個結果計算尾隨零的數目，然后計算所需的和。此方法的復雜度為 O（m * n），因為對于給定的 m 個查詢，我們將對整個數組進行 m 次操作，并且將需要額外的大小為 m 的空間來保存在類型 3 查詢中獲得的結果用于在執行 m 個查詢后計算尾隨零的數量。因此，時間復雜度為 O（m * n），空間復雜度為 O（m）。 **方法 2**：在此方法中，我們有 2 個向量，因為帶尾隨零的數字可以是 10 的倍數，而 10 則是 2 和 5 的倍數，因此為此目的保留了兩個單獨的向量。其余內容將在下面說明。 ``` // CPP program to solve three types of queries. #include <bits/stdc++.h> using namespace std; //vector of 1000 elements,? //all set to 0 vector<int> twos(1000,0); //vector of 1000 elements,? //all set to 0? vector<int> fives(1000,0); int sum = 0; // Function to check number of // trailing zeros in multiple of 2 int returnTwos(int val) { ????int count = 0; ????while (val % 2 == 0 && val != 0) { ????????val = val / 2; ????????count++; ????} ????return count; } // Function to check number of // trailing zeros in multiple of 5 int returnFives(int val) { ????int count = 0; ????while (val % 5 == 0 && val != 0) { ????????val = val / 5; ????????count++; ????} ????return count; } // Function to solve the queries received void solve_queries(int arr[], int n) { ????int type, ql, qr, x, y; ????cin >> type; ????// If the query is of type 1\. ????if (type == 1) { ????????cin >> ql >> qr >> x; ????????// Counting the number of ????????// zeros in the given value of x ????????int temp = returnTwos(x); ????????int temp1 = returnFives(x); ????????for (int i = ql - 1; i < qr; i++) { ????????????// The value x has been multiplied ????????????// to their respective indices ????????????arr[i] = arr[i] * x; ????????????// The value obtained above has been ????????????// added to their respective vectors ????????????twos[i] += temp; ????????????fives[i] += temp1; ????????} ????} ????// If the query is of type 2\. ????if (type == 2) { ????????cin >> ql >> qr >> y; ????????// Counting the number of ????????// zero in the given value of x ????????int temp = returnTwos(y); ????????int temp1 = returnFives(y); ????????for (int i = ql - 1; i < qr; i++) { ????????????// The value y has been replaced ????????????// to their respective indices ????????????arr[i] = (i - ql + 2) * y; ????????????// The value obtained above has been ????????????// added to their respective vectors ????????????twos[i] = returnTwos(i - ql + 2) + temp; ????????????fives[i] = returnFives(i - ql + 2) + temp1; ????????} ????} ????// If the query is of type 2 ????if (type == 3) { ????????cin >> ql >> qr; ????????int sumtwos = 0; ????????int sumfives = 0; ????????for (int i = ql - 1; i < qr; i++) { ????????????// as the number of trailing zeros for ????????????// each case has been found for each array? ????????????// element then we simply add those to ????????????// the respective index to a variable ????????????sumtwos += twos[i]; ????????????sumfives += fives[i]; ????????} ????????// Compare the number of zeros ????????// obtained in the multiples of five and two ????????// consider the minimum of them and add them ????????sum += min(sumtwos, sumfives); ????} } // Driver code int main() { ????int n, m; ????// Input the Size of array ????// and number of queries ????cin >> n >> m; ????int arr[n]; ????for (int i = 0; i < n; i++) { ????????cin >> arr[i]; ????????twos[i] = returnTwos(arr[i]); ????????fives[i] = returnFives(arr[i]); ????} ????// Running the while loop ????// for m number of queries ????while (m--) { ????????solve_queries(arr, n); ????} ????cout << sum << endl; ????return 0; } ``` 輸入： ``` 5 5 2 4 3 5 5 3 2 4 3 2 5 2 2 4 1 1 3 3 10 3 1 5 ``` 輸出： ``` 5 ``` 此代碼的復雜度為`O(n)`。本文由 [**Mohak Agrawal**](https://auth.geeksforgeeks.org/profile.php?user=agrawalmohak99&list=practice) 貢獻。如果您喜歡 GeeksforGeeks 并希望做出貢獻，您還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。