用于乘法，替换和乘积的数组查询 · 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。