!Please take care hints!"T-Generation" has decided to purchase gifts for various needs;…
- User
!Please take care hints!"T-Generation" has decided to purchase gifts for various needs; thus, they have n different sweaters numbered from 1 to n . The i -th sweater has a size of ai . Now they need to send some subsegment of sweaters to an olympiad. It is necessary that the sweaters fit as many people as possible, but without having to take too many of them.
They need to choose two indices l and r (1≤l≤r≤n ) to maximize the convenience equal to max(al,al+1,…,ar)−min(al,al+1,…,ar)−(r−l), that is, the range of sizes minus the number of sweaters.
Sometimes the sizes of the sweaters change; it is known that there have been q changes, in each change, the size of the p -th sweater becomes x .
Help the "T-Generation" team and determine the maximum convenience among all possible pairs (l,r) initially, as well as after each size change.
Input Each test consists of several test cases. The first line contains a single integer t (1≤t≤104 ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers n and q (1≤n,q≤2⋅105 ) — the number of sweaters and the number of size changes.
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109 ) — the sizes of the sweaters.
Each of the following q lines of each test case contains two integers p and x (1≤p≤n , 1≤x≤109 ) — the next size change.
It is guaranteed that the sum of the values of n and the sum of the values of q across all test cases do not exceed 2⋅105 .
Output For each test case, output the maximum value of convenience among all possible pairs (l,r) before any actions, as well as after each size change.
Example InputCopy 3 2 2 1 10 1 10 2 2 5 3 1 2 3 4 5 3 7 1 4 5 2 8 5 7 4 2 4 8 2 1 4 5 4 1 10 3 2 8 11 7 7 OutputCopy 8 0 7 0 4 4 4 5 3 6 6 9 7 Note Consider the first test case.
Before any changes, you can take all the sweaters; then the convenience is equal to max(a1,a2)−min(a1,a2)−(2−1)=10−1−1=8 . After the first query, the sizes of both sweaters will be equal to 10 , you can only take the first sweater and the convenience is equal to 10−10−0=0 . After the second query, the size of the first sweater will be 10 , and the second 2 , you can take all the sweaters and the convenience is equal to max(a1,a2)−min(a1,a2)−(2−1)=10−2−1=7 .!Hint 1: Utilize Efficient Data Structures for Range Queries To maximize the convenience, which involves calculating the range (max - min) for various subsegments, you need a way to efficiently query the maximum and minimum values within any given range.
Segment Trees or Sparse Tables: Implement a segment tree or a sparse table to perform range maximum and range minimum queries in logarithmic or constant time. This allows you to quickly evaluate the convenience for different subsegments without recalculating max and min from scratch each time. Preprocessing: Preprocess the array to build these data structures before handling any queries or updates. Efficient preprocessing ensures that subsequent queries can be answered swiftly, which is crucial given the potential number of changes. By leveraging these data structures, you can handle range queries effectively, enabling you to evaluate the convenience for all possible subsegments quickly.Hint 2: Optimize Handling of Updates and Maintainability Since the sweater sizes can change multiple times, it's essential to ensure that your solution can handle updates efficiently while still allowing quick queries for maximum convenience.
Dynamic Updates: Choose data structures that support dynamic updates, such as segment trees with update operations, to reflect changes in sweater sizes promptly. This ensures that after each update, you can still perform accurate range queries without rebuilding the entire structure. Balancing Update and Query Efficiency: Ensure that both update and query operations are optimized to run within acceptable time limits, especially when dealing with a large number of operations. Consider the trade-offs between different data structures to find the most efficient approach for your specific use case. By focusing on efficient update mechanisms and maintaining the integrity of your range queries, you can ensure that your solution remains performant even as the sweater sizes undergo multiple changes.! c++
- Assistant
To solve this problem, we need an efficient way to compute the maximum convenience, defined as ((\text{max} - \text{min}) - (r - l)), where (\text{max}) and (\text{min}) are the maximum and minimum sweater sizes in the subsegment from (l) to (r). We need to process updates to the sweater sizes and recalculate the maximum convenience after each update.
Here's the approach:
-
Observation: The convenience depends on the maximum and minimum values and the positions where they occur. Specifically, we can consider pairs of positions where the maximum and minimum values occur and compute the convenience as ((\text{max} - \text{min}) - |i - j|), where (i) and (j) are the positions of the maximum and minimum values, respectively.
-
Implementation:
- Initial Setup:
- Store the maximum and minimum values and their positions.
- Since there could be multiple occurrences, keep a list of positions for both the maximum and minimum values.
- Compute Initial Convenience:
- Iterate over the positions where the maximum and minimum values occur.
- Compute the convenience for each pair and maintain the maximum convenience.
- Processing Updates:
- For each update:
- Update the sweater size at the specified position.
- Update the lists of positions for the maximum and minimum values if necessary.
- Recalculate the maximum convenience using the updated maximum and minimum values and their positions.
- For each update:
- Initial Setup:
-
Efficiency:
- By focusing only on the positions where the maximum and minimum values occur, we reduce the computations significantly.
- Since the number of positions for maximum and minimum values is typically small, the algorithm runs efficiently within the given constraints.
Here is the C++ code implementing the above approach:
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <set> #include <cmath> #include <climits> using namespace std; void solve() { int t; cin >> t; while (t--) { int n, q; cin >> n >> q; vector<int> a(n+1); map<int, vector<int>> pos_map; int max_val = INT_MIN; int min_val = INT_MAX; for (int i = 1; i <= n; i++) { cin >> a[i]; max_val = max(max_val, a[i]); min_val = min(min_val, a[i]); } pos_map.clear(); for (int i = 1; i <= n; i++) { pos_map[a[i]].push_back(i); } int max_convenience = INT_MIN; if (max_val != min_val) { vector<int>& max_positions = pos_map[max_val]; vector<int>& min_positions = pos_map[min_val]; int min_distance = INT_MAX; int i = 0, j = 0; while (i < max_positions.size() && j < min_positions.size()) { int idx1 = max_positions[i]; int idx2 = min_positions[j]; int distance = abs(idx1 - idx2); if (distance < min_distance) { min_distance = distance; } if (idx1 < idx2) i++; else j++; } max_convenience = max_val - min_val - min_distance; } else { max_convenience = 0; } cout << max_convenience << endl; while (q--) { int p, x; cin >> p >> x; int old_val = a[p]; a[p] = x; // Update position maps auto& old_positions = pos_map[old_val]; old_positions.erase(remove(old_positions.begin(), old_positions.end(), p), old_positions.end()); if (old_positions.empty()) pos_map.erase(old_val); pos_map[x].push_back(p); sort(pos_map[x].begin(), pos_map[x].end()); // Update max and min values max_val = max(max_val, x); min_val = min(min_val, x); if (pos_map.find(old_val) == pos_map.end()) { if (old_val == max_val || old_val == min_val) { // Recalculate max_val and min_val if (!pos_map.empty()) { max_val = prev(pos_map.end())->first; min_val = pos_map.begin()->first; } else { max_val = min_val = INT_MIN; } } } // Recalculate convenience if (max_val != min_val) { vector<int>& max_positions = pos_map[max_val]; vector<int>& min_positions = pos_map[min_val]; int min_distance = INT_MAX; int i = 0, j = 0; while (i < max_positions.size() && j < min_positions.size()) { int idx1 = max_positions[i]; int idx2 = min_positions[j]; int distance = abs(idx1 - idx2); if (distance < min_distance) { min_distance = distance; } if (idx1 < idx2) i++; else j++; } max_convenience = max_val - min_val - min_distance; if (max_convenience < 0) max_convenience = 0; } else { max_convenience = 0; } cout << max_convenience << endl; } } } int main() { solve(); return 0; }Explanation:
- We maintain a
mapcalledpos_mapthat stores the positions for each value. - We keep track of the current maximum and minimum values in the array.
- When an update occurs:
- We remove the old position from the positions list of the old value.
- We add the new position to the positions list of the new value.
- We update the maximum and minimum values if necessary.
- To compute the maximum convenience, we find the minimum distance between any occurrence of the maximum and minimum values.
- We output the maximum convenience after initial setup and after each update.
This solution efficiently handles both the initial calculation and the updates within acceptable time constraints for the problem.
-