专栏文章

题解：P13787 地毯 加强版

wweichenglu
P13787题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mio7lthg
此快照首次捕获于
2025/12/02 14:40
3 个月前
此快照最后确认于
2025/12/02 14:40
3 个月前
查看原文

题目描述

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

思路分析

方法一（TLE）

最简单的方法即为暴力。使用二维数组 aa 记录每个格子的地毯覆盖数，每次遍历地毯所覆盖的每一个格子。
CPP
#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(n2m)O(n^2m)，观察数据范围，很明显会超时。

方法二（50 Pts）

我们考虑减少读入地毯时的一层循环，由于涉及到区间求和，我们可以考虑使用差分。
可以将地图看成 nn 个大小为 nn 的一维数组，使用一维差分。
假设一个一维数组 dd，一维差分的方法为：
  1. 对于所有 1≤i≤n1 \le i \le n，预处理出 di←di−di−1d_i \gets d_i - d_{i-1}。（由于本题初始数组元素都为 00，所以无需进行此操作）
  2. 读入 ll 与 rr，修改此区间的两个端点的值，使 dld_l 加 11，dr+1d_{r+1} 减 11。
  3. 每行从左往右扫描一遍，跑一遍一维前缀和，即使 di←di+di−1d_i \gets d_i + d_{i-1}，就可以得到每个格子的地毯覆盖数。
代码如下：
CPP
#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(n2+nm)O(n^2+nm)，观察数据范围，很明显依旧无法被接受。

方法三（100 Pts）

由于此题 m≤2×105m \le 2\times 10^5，所以对于读入地毯还需再压掉一维，即将读入地毯的时间复杂度压为 O(m)O(m)，于是我们需要使用二维差分。
假设一个二维数组 dd，二维差分的方法为：
  1. 对于所有 1≤i≤n1 \le i \le n 与 1≤j≤n1 \le j \le n，预处理出 di,j←di,j−di−1,j−di,j−1+di−1,j−1d_{i,j} \gets d_{i,j} - d_{i-1,j} - d_{i,j-1} + d_{i-1,j-1}。（由于本题初始数组元素都为 00，所以无需进行此操作）
  2. 读入 x1x1、y1y1、x2x2 与 y2y2，修改此矩形的四个端点的值，使 dx1,y1d_{x1,y1} 加 11，dx1,y2+1d_{x1,y2+1} 减 11，dx2+1,y1d_{x2+1,y1} 减 11，dx2+1,y2+1d_{x2+1,y2+1} 加 11。
  3. 从上到下、从左往右扫描一遍，跑一遍二维前缀和，即使 di,j←di,j+di−1,j+di,j−1−di−1,j−1d_{i,j} \gets d_{i,j} + d_{i-1,j} + d_{i,j-1} - d_{i-1,j-1}，就可以得到每个格子的地毯覆盖数。
代码如下：
CPP
#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;
        a[x1][y1]++;
        a[x1][y2+1]--;
        a[x2+1][y1]--;
        a[x2+1][y2+1]++;
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=n;++j){
            a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1]; 
            sum += (i + j) ^ a[i][j];
        }
    }
    cout << sum;
	
	return 0;
}
此代码的时间复杂度为 O(n2+m)O(n^2+m)，可以通过此题。

注意

不开 long long 见祖宗

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...