## Intuition The problem requires us to determine the total area of rectangles that can fit within certain constraints defined by each query. The key insight is to efficiently precompute and store the areas of rectangles in a way that allows us to quickly answer each query. Given the constraints, a direct approach of checking each rectangle for every query would be too slow. Instead, we can leverage the fact that the maximum height and width are both 1000, allowing us to use a 2D prefix sum array to efficiently compute the sum of areas for rectangles that fit the query constraints. ## Approach 1. **Preprocessing with a 2D Prefix Sum Array:** - Create a 2D array `areaSum` where `areaSum[h][w]` stores the total area of all rectangles with height `h_i <= h` and width `w_i <= w`. - Iterate over each rectangle and update `areaSum[h_i][w_i]` by adding the area of the rectangle `h_i * w_i`. - Compute the prefix sums over this 2D array so that `areaSum[h][w]` gives the sum of areas of all rectangles with height and width less than or equal to `h` and `w`. 2. **Answering Queries:** - For each query `(h_s, w_s, h_b, w_b)`, calculate the sum of areas of rectangles that fit the constraints using the precomputed `areaSum`: - Use inclusion-exclusion principle to compute the sum of areas for rectangles where `h_s < h_i < h_b` and `w_s < w_i < w_b`. - The formula is: ``` areaSum[h_b - 1][w_b - 1] - areaSum[h_s][w_b - 1] - areaSum[h_b - 1][w_s] + areaSum[h_s][w_s] ``` 3. **Output the Results:** - For each query, compute the result using the above formula and output it. ## Complexity - **Time Complexity:** - Preprocessing the `areaSum` array takes `O(n + H * W)` where `H` and `W` are the maximum height and width (1000). - Each query is answered in `O(1)` using the precomputed prefix sums. - Overall complexity per test case is `O(n + q + H * W)`. - **Space Complexity:** - The space complexity is `O(H * W)` for storing the `areaSum` array. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; const int MAX_HW = 1000; while (t--) { int n, q; cin >> n >> q; vector> areaSum(MAX_HW + 1, vector(MAX_HW + 1, 0)); for (int i = 0; i < n; ++i) { int h, w; cin >> h >> w; areaSum[h][w] += h * w; } // Compute prefix sums for (int h = 1; h <= MAX_HW; ++h) { for (int w = 1; w <= MAX_HW; ++w) { areaSum[h][w] += areaSum[h - 1][w] + areaSum[h][w - 1] - areaSum[h - 1][w - 1]; } } for (int i = 0; i < q; ++i) { int h_s, w_s, h_b, w_b; cin >> h_s >> w_s >> h_b >> w_b; long long result = areaSum[h_b - 1][w_b - 1] - areaSum[h_s][w_b - 1] - areaSum[h_b - 1][w_s] + areaSum[h_s][w_s]; cout << result << "\n"; } } return 0; } ``` This solution efficiently handles each test case by leveraging a 2D prefix sum array, allowing us to quickly compute the required area sums for each query.

Counting Rectangles

Problem Details