E. Counting Rectangles - 题解

比赛与标签

比赛: Codeforces Round 817 (Div. 4) 标签: brute force, data structures, dp, implementation 难度: *1600

题目大意喵~

主人，你好喵~！这道题是要我们当一个矩形收藏家呢！

我们手上有 n 个不同尺寸的矩形，每个矩形有自己的高度 h 和宽度 w。然后会有 q 次查询，每次查询会给我们四个数字 hs, ws, hb, wb。

对于每一次查询，我们需要找出我们收藏的所有矩形中，满足下面这些条件的矩形，并计算出它们面积的总和：

这个矩形的高度 hi 必须大于 hs。
这个矩形的宽度 wi 必须大于 ws。
这个矩形的高度 hi 必须小于 hb。
这个矩形的宽度 wi 必须小于 wb。

简单来说，就是找出所有满足 hs < hi < hb 且 ws < wi < wb 的矩形，然后把它们的面积 hi * wi 全部加起来。

最后要注意，答案可能会很大很大，要用 long long 来存哦！

解题思路大揭秘！

每次查询都遍历一遍所有的矩形？哼哼，那可太慢了喵！n 和 q 都可能达到 10^5，如果每次查询都检查 n 个矩形，总操作次数会是 n * q，这绝对会超时的说！

所以，我们需要更聪明的办法！既然查询这么多，我们不如先花点时间把信息整理好，这样每次查询就能光速回答啦！这是一种“预处理”的思想。

主人请看，题目里矩形的高和宽最大都只有 1000，这个范围其实不大，是不是在暗示我们什么呢？喵~

没错！我们可以利用这个特点，建立一个二维的“地图”或者说“棋盘”。

建立信息网格：我们可以想象一个 1001x1001 的巨大网格，我们叫它 areas 好了。网格的每个格子 areas[h][w] 用来记录一件事：所有高度为 h、宽度为 w 的矩形的面积总和。
预处理第一步：填充网格：我们先遍历输入的 n 个矩形。对于每一个矩形 (hi, wi)，我们就把它自己的面积 hi * wi 加到 areas[hi][wi] 这个格子里去。这样，遍历完所有 n 个矩形后，我们的 areas 网格就包含了所有矩形按尺寸分类的面积信息啦！
预处理第二步：加速查询的秘密武器——二维前缀和！ 现在，对于一个查询 hs, ws, hb, wb，我们实际上是想求 areas 网格中，一个由 (hs+1, ws+1) 作为左上角、(hb-1, wb-1) 作为右下角的矩形区域内，所有数值的总和。如果每次查询都去遍历这个子区域来求和，还是有点慢。
这时候，我们的终极秘密武器——二维前缀和 (2D Prefix Sum) 就要登场啦！
我们再创建一个 1001x1001 的网格，叫做 prefix_sum。prefix_sum[i][j] 用来存储 areas 网格中，从左上角 (1, 1) 到 (i, j) 这个大矩形区域内所有值的总和。
这个 prefix_sum 网格可以很方便地通过递推计算出来： prefix_sum[i][j] = areas[i][j] + prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1] 这个公式的含义是：(i,j) 的前缀和 = 当前格子的值 + 上方区域的和 + 左方区域的和 - 左上方被重复计算区域的和。这就是经典的容斥原理哦！
O(1) 回答查询：有了 prefix_sum 这个魔法表格，查询任何一个子矩形区域的和就只需要 O(1) 的时间！我们还是利用容斥原理：
目标区域的和 = (右下角大矩形) - (其上方多余的大矩形) - (其左方多余的大矩形) + (左上角被重复减掉的小矩形)
对应到我们的查询 hs < h < hb 和 ws < w < wb，也就是 hs+1 <= h <= hb-1 和 ws+1 <= w <= wb-1，用前缀和公式计算就是： ans = prefix_sum[hb-1][wb-1] - prefix_sum[hs][wb-1] - prefix_sum[hb-1][ws] + prefix_sum[hs][ws]
看，是不是和代码一模一样呀？通过两步预处理，我们成功地将每次查询的时间复杂度降到了常数级别，太棒了喵！

代码实现喵~

cpp

#include <iostream>

// 使用全局数组可以避免栈溢出喵，而且全局数组会自动初始化为0
// 矩形尺寸最大是1000，所以数组大小至少要1001
// areas[h][w] 用来存储所有高为h、宽为w的矩形的面积总和
long long areas[1001][1001];
// prefix_sum[h][w] 用来存储从(1,1)到(h,w)这个矩形区域内所有面积的总和
long long prefix_sum[1001][1001];

void solve() {
    int n, q;
    std::cin >> n >> q;

    // 非常重要的一步！因为是多组测试用例，必须把上次计算的areas网格清空
    // 我们只需要清理可能被用到的部分就够了
    for (int i = 1; i <= 1000; ++i) {
        for (int j = 1; j <= 1000; ++j) {
            areas[i][j] = 0;
        }
    }

    // 第一步：读取n个矩形，填充areas网格
    for (int i = 0; i < n; ++i) {
        int h, w;
        std::cin >> h >> w;
        // 把这个矩形的面积加到对应的格子里
        areas[h][w] += static_cast<long long>(h) * w;
    }

    // 第二步：构建二维前缀和数组
    // 全局数组的第0行和第0列默认为0，正好作为递推的边界条件
    for (int i = 1; i <= 1000; ++i) {
        for (int j = 1; j <= 1000; ++j) {
            prefix_sum[i][j] = areas[i][j] + prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1];
        }
    }

    // 第三步：处理q次查询
    for (int k = 0; k < q; ++k) {
        int hs, ws, hb, wb;
        std::cin >> hs >> ws >> hb >> wb;

        // 我们需要求和的范围是 h in (hs, hb) 和 w in (ws, wb)
        // 也就是 h 从 hs+1 到 hb-1，w 从 ws+1 到 wb-1
        // 使用二维前缀和与容斥原理来 O(1) 计算子矩形和
        // Sum(r1..r2, c1..c2) = P(r2,c2) - P(r1-1,c2) - P(r2,c1-1) + P(r1-1,c1-1)
        // 这里, r1=hs+1, c1=ws+1, r2=hb-1, c2=wb-1.
        // 所以, r1-1=hs, c1-1=ws.
        long long ans = prefix_sum[hb - 1][wb - 1] - prefix_sum[hs][wb - 1] - prefix_sum[hb - 1][ws] + prefix_sum[hs][ws];
        std::cout << ans << "\n";
    }
}

int main() {
    // 加速输入输出，让程序跑得更快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析的说

时间复杂度: O(N + MAX_H * MAX_W + Q) 的说。
- 对于每个测试用例，我们首先用 O(N) 的时间读取输入并填充 areas 数组。
- 然后用 O(MAX_H * MAX_W) 的时间，也就是 O(1000 * 1000)，来构建二维前缀和数组。
- 最后，每个查询只需要 O(1) 的时间，总共 Q 次查询就是 O(Q)。
- 所以总时间复杂度是 O(N + 1000*1000 + Q)，这对于本题的数据范围来说是绰绰有余的！
空间复杂度: O(MAX_H * MAX_W) 的说。
- 我们开了两个 1001x1001 的二维数组 areas 和 prefix_sum 来存储数据。
- 所以空间复杂度是 O(1000*1000) 呐。还好内存限制是256MB，足够我们挥霍啦，喵~

知识点与总结

这道题真是太有趣啦，完美地展示了如何用预处理来优化查询效率！

核心思想：预处理 + 快速查询 当遇到有大量查询，且查询范围有规律的问题时，可以考虑先花一些时间构建一个方便查询的数据结构，从而大大降低每次查询的成本。
关键数据结构：二维前缀和 这是本题的灵魂所在！它能把对一个二维区域求和的复杂度从 O(H*W) 降到神奇的 O(1)，是处理二维网格上区域查询问题的超级利器！
数学原理：容斥原理 在计算二维前缀和以及用它查询子矩形和的时候，我们都用到了加加减减的容斥原理，这是组合数学里一个非常有用的工具，要好好掌握哦。
编程小贴士
- 多组测试用例：如果使用了全局变量，一定要记得在每个测试用例开始时进行初始化或清空！
- 数据范围：题目中 1 <= h, w <= 1000 是一个非常强的暗示，引导我们使用二维数组来解决问题。
- 数据类型：计算面积和时，结果可能会超过 int 的范围，要记得使用 long long 防止溢出。

掌握了二维前缀和，以后遇到类似的二维区域查询问题就再也不怕啦！继续加油哦，主人！喵~

E. Counting Rectangles - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大揭秘！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​