You are given two arrays of integers a and b, and an array queries. The elements of…
- User
You are given two arrays of integers
aandb, and an arrayqueries. The elements ofqueriesare queries you are required to process. Everyqueries[i]can have one of the following two forms:[0, i, x]: In this case, you need to assigna[i]the value ofx(a[i] = x).[1, x]: In this case, you need to find the total number of pairs of indicesiandjsuch thata[i] + b[j] = x.
Perform the given queries in order and return an array containing the results of the queries of the type
[1, x].Example
- For
a = [3, 4],b = [1, 2, 3], andqueries = [[1, 5], [0, 0, 1], [1, 5]], the output should besolution(a, b, queries) = [2, 1].
The arrays look like this initially:
a = [3, 4] and b = [1, 2, 3]For the query
[1, 5], there are two ways to form a sum of 5 using an element from each array:5 = 3 + a[0] + b[1]and5 = 4 + a[1] = 1 + b[0]. So the result is 2.The query
[0, 0, 1]re-assigns the value ofa[0]to 1, so the arrays now look like this:a = [1, 4] and b = [1, 2, 3]For the final
[1, 5]query, there's now only one way to form the sum of 5 using an element from each array:5 = 4 + a[1] = 1 + b[0]. So the result is 1.Since the two queries of type
[1, x]gave results of 2 and 1 respectively, the answer is[2, 1].- For
a = [2, 3],b = [1, 2, 2], andqueries = [[1, 4], [0, 0, 3], [1, 5]], the output should besolution(a, b, queries) = [3, 4].
The arrays look like this initially:
a = [2, 3] and b = [1, 2, 2]For the query
[1, 4], there are three ways to form a sum of 4 using an element from each array:4 = 2 + a[0] + b[1] = 2 + a[0] + b[2], and4 = 3 + a[1] = 1 + b[0]. So the result is 3.The query
[0, 0, 3]reassigns the value ofa[0]to 3, so the arrays now look like this:a = [3, 3] and b = [1, 2, 2]For the query
[1, 5], there are now 4 ways to form a sum of 5 using an element from each array:5 = 3 + a[0] = 2 + b[1], 5 = 3 + a[0] = 2 + b[2], 5 = 3 + a[1] = 2 + b[1], and5 = 3 + a[1] = 2 + b[2]. So the result is 4.Since the two queries of type
[1, x]gave results of 3 and 4 respectively, the answer is[3, 4].Input/Output
-
[execution time limit] 0.5 seconds (cpp)
-
[memory limit] 1 GB
-
[input] array.integer a An array of integers.
Guaranteed constraints:
1 ≤ a.length ≤ 5 * 10^4,0 ≤ a[i] ≤ 10^9.- [input] array.integer b An array of integers.
Guaranteed constraints:
1 ≤ b.length ≤ 5 * 10^4,0 ≤ b[i] ≤ 10^9.- [input] array.array.integer queries An array of queries.
Guaranteed constraints:
1 ≤ queries.length ≤ 10^5.- [output] array.integer
An array containing the results of the queries of the type
[1, x].
solve this and give me best optimized solution for this in cpp
- Assistant
To solve this problem efficiently, we'll utilize hash maps to keep track of frequencies for both arrays
aandb. We'll take advantage of the fact that arraybdoesn't change, so we can pre-process and store the counts of its elements.Here's the step-by-step plan:
-
Value Compression: Since the values can be large (up to
1e9), we'll use value compression by mapping the unique values inaandb(including all potential update values fromqueries) to a continuous range of indices. -
Frequency Maps:
- Create a frequency map for
b,count_b, wherecount_b[val]stores the number of timesvalappears inb. - Create a frequency map for
a,count_a, wherecount_a[val]keeps track of the counts of each unique value ina.
- Create a frequency map for
-
Process Queries:
- For each query:
- If it's an update query
[0, i, x]:- Update the counts in
count_aby decrementing the count of the old value ata[i]and incrementing the count of the new valuex. - Update the value at
a[i].
- Update the counts in
- If it's a sum query
[1, x]:- Calculate the total number of pairs by iterating over the unique values in
count_a. - For each unique value
val_aincount_a:val_b = x - val_a- If
val_bexists incount_b, addcount_a[val_a] * count_b[val_b]to the total.
- Calculate the total number of pairs by iterating over the unique values in
- If it's an update query
- For each query:
-
Optimization:
- Although iterating over all unique values in
count_acan be up toN, in practice, the counts of unique values are often much smaller. - This approach reduces the time complexity per query to
O(N_unique_a). - Since updates only affect
a, and notb, this strategy minimizes redundant computations.
- Although iterating over all unique values in
Here's the C++ code implementing the above plan:
#include <iostream> #include <vector> #include <unordered_map> #include <unordered_set> using namespace std; vector<int> solution(vector<int>& a, vector<int>& b, vector<vector<int>>& queries) { // Collect all unique values from a, b, and updates in queries unordered_set<int> unique_vals; for (int val : a) unique_vals.insert(val); for (int val : b) unique_vals.insert(val); for (const auto& query : queries) { if (query[0] == 0) { unique_vals.insert(query[2]); // Updates to a[i] can introduce new values } else { // Not collecting x values since they may be too many // Alternatively, we could optimize based on unique x values if they are few } } // Map values to compressed indices unordered_map<int, int> val_to_compressed; int idx = 0; for (int val : unique_vals) { val_to_compressed[val] = idx++; } // Prepare count_b with compressed indices vector<int> count_b(idx, 0); for (int val : b) { count_b[val_to_compressed[val]]++; } // Prepare initial count_a with compressed indices vector<int> count_a(idx, 0); for (int i = 0; i < a.size(); ++i) { a[i] = val_to_compressed[a[i]]; // Update a[i] to compressed value count_a[a[i]]++; } vector<int> result; for (const auto& query : queries) { if (query[0] == 0) { // Update query int i = query[1]; int new_val = query[2]; new_val = val_to_compressed[new_val]; // Get compressed index int old_val = a[i]; count_a[old_val]--; count_a[new_val]++; a[i] = new_val; } else { // Sum query int x = query[1]; long long total = 0; // For all unique val_a in count_a for (int val_a = 0; val_a < idx; ++val_a) { if (count_a[val_a] == 0) continue; int val_b_actual = x - unique_vals[val_a]; // Get actual value of val_a if (val_to_compressed.find(val_b_actual) != val_to_compressed.end()) { int val_b = val_to_compressed[val_b_actual]; if (val_b >= 0 && val_b < idx) { total += (long long)count_a[val_a] * count_b[val_b]; } } } result.push_back(total); } } return result; }Explanation:
- We first collect all unique values from
a,b, and potential updates to map them to compressed indices. - We update
ato use compressed indices so that we can use index-based access in thecount_avector. - For sum queries, we iterate over the non-zero counts in
count_aand check if the correspondingval_bexists incount_b. - We use the actual values when computing
x - val_asince ourval_to_compressedmap maps actual values to compressed indices, and we need to retrieve the compressed index forval_b. - The use of
long longensures that we can handle large totals without integer overflow.
This solution keeps the per-query time complexity acceptable by avoiding per-element iteration whenever possible and utilizing hash maps for constant-time lookups.
-