题解：P13787 地毯加强版

weichenglu · 2025-08-21 15:42:44 · 题解

题目描述

在 n\times n 的地图上，有 m 条地毯，求每个格子上的地毯覆盖数。

思路分析

方法一（TLE）

最简单的方法即为暴力。使用二维数组 a 记录每个格子的地毯覆盖数，每次遍历地毯所覆盖的每一个格子。

#include <bits/stdc++.h>
#define N 5005
#define int long long
using namespace std;

int n,m;
int a[N][N];
int sum;

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i=1;i<=m;++i){
        int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
        for (int x=x1;x<=x2;++x){
            for (int y=y1;y<=y2;++y){
                a[x][y]++;
            }
        }
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=n;++j){
            sum += (i + j) ^ a[i][j];
        }
    }
    cout << sum;

    return 0;
}

这样实现的时间复杂度为 O(n^2m)，观察数据范围，很明显会超时。

方法二（50 Pts）

我们考虑减少读入地毯时的一层循环，由于涉及到区间求和，我们可以考虑使用差分。
可以将地图看成 n 个大小为 n 的一维数组，使用一维差分。
假设一个一维数组 d，一维差分的方法为：

对于所有 1 \le i \le n，预处理出 d_i \gets d_i - d_{i-1}。（由于本题初始数组元素都为 0，所以无需进行此操作）
读入 l 与 r，修改此区间的两个端点的值，使 d_l 加 1，d_{r+1} 减 1。
每行从左往右扫描一遍，跑一遍一维前缀和，即使 d_i \gets d_i + d_{i-1}，就可以得到每个格子的地毯覆盖数。

代码如下：

#include <bits/stdc++.h>
#define N 5005
#define int long long
using namespace std;

int n,m;
int a[N][N];
int sum;

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i=1;i<=m;++i){
        int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
        for (int j=x1;j<=x2;++j) a[j][y1]++,a[j][y2+1]--;
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=n;++j){
            a[i][j] += a[i][j-1];
            sum += (i + j) ^ a[i][j];
        }
    }
    cout << sum;

    return 0;
}

但是，这样实现的时间复杂度为 O(n^2+nm)，观察数据范围，很明显依旧无法被接受。

方法三（100 Pts）

由于此题 m \le 2\times 10^5，所以对于读入地毯还需再压掉一维，即将读入地毯的时间复杂度压为 O(m)，于是我们需要使用二维差分。

假设一个二维数组 d，二维差分的方法为：

对于所有 1 \le i \le n 与 1 \le j \le n，预处理出 d_{i,j} \gets d_{i,j} - d_{i-1,j} - d_{i,j-1} + d_{i-1,j-1}。（由于本题初始数组元素都为 0，所以无需进行此操作）
读入 x1、y1、x2 与 y2，修改此矩形的四个端点的值，使 d_{x1,y1} 加 1，d_{x1,y2+1} 减 1，d_{x2+1,y1} 减 1，d_{x2+1,y2+1} 加 1。
从上到下、从左往右扫描一遍，跑一遍二维前缀和，即使 d_{i,j} \gets d_{i,j} + d_{i-1,j} + d_{i,j-1} - d_{i-1,j-1}，就可以得到每个格子的地毯覆盖数。