专栏文章

题解：P13787 地毯 加强版

zzybgml_AFO
P13787题解参与者 9已保存评论 9

文章操作

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

当前评论
9 条
当前快照
1 份
快照标识符
@mio7hbse
此快照首次捕获于
2025/12/02 14:37
3 个月前
此快照最后确认于
2025/12/02 14:37
3 个月前
查看原文
题目链接：P13787 地毯 加强版

题目大意

给你一个有 n×nn\times n 个格子的坐标，再在上面铺 mm 块地毯，问你每个位置的行数加列数异或被多少个地毯覆盖的和。

做法1：暴力

我们利用一个二维数组来记录每个点被多少个地毯覆盖，最后按要求输出。可是那样的话，时间复杂度度太高了，有没有更简单且高效的方法呢？
有的兄弟，有的。想修改区间值的话 二维差分 是一个十分简单的方法。

正解：二维前缀和 ++ 二维差分

相关知识：一维前缀和 ++ 一维差分

一维前缀和

假如给你一个数组，你有没有一种可以用 O(1)O(1) 的时间复杂度求出其中的任意一个区间和的方法呢？一维前缀和 是一种可以只用时间复杂度为 O(n)O(n) 预处理就可以用 O(1)O(1) 的时间复杂度求出任意区间和的方法。它的原理简单易懂：
我们将数组中第 ii 个数变成前 ii 个数的总和，这样就完成预处理啦！
所以现在如何求区间和呢？假如有 55 个数：
CPP
1 2 3 4 5
预处理后 55 个数为：
CPP
1 3 6 10 15
而如果我们要求区间 [2,4][2,4] 的总和，只需要用预处理后的第 44 个数减去第 11 个数就可以了！
为什么呢？其实原理非常简单：预处理后的第 44 个数为前 44 个数的总和，第 11 个数为前 11 个数的总和。两者相减，不就是第 22 个数至第 44 个数的总和吗？
可是如果我们还要先更改区间值又该如何呢？
一维差分 可以帮你解决此问题：

一维差分

同样 55 个数：
CPP
1 2 3 4 5
我们要将区间 [2,4][2,4] 中的每一个数都加上 11 该如何做呢？
一维差分 同样需要先用时间复杂度为 O(n)O(n) 的预处理，使原数组的第 ii 个数为前 ii 个数的总和： 预处理后 55 个数为：
CPP
1 1 1 1 1
也就是说，本来的数组为现在预处理后的数组的前缀和数组！
现在，如果我们将第 22 个数加上 11 的话，本来的数组会有什么变化呢？
CPP
1 3 4 5 6
不难发现，从第 22 个数开始，每个数都加了 11。
聪明的人已经看出，现在我们只要将第 55 个数加上 −1-1，就完成了将区间 [2,4][2,4] 中的每一个数都加上 11 的操作。
原因是我们通过反向利用 一维前缀和 ，来高效修改了区间值。

二维前缀和

懂了 一维前缀和 的相信很快也能理解 二维前缀和。
二维前缀和 其实也很好推，这里不举例了。
假如有一个二维数组，我们要求 (1,1)(1,1) 至 (x,y)(x,y) 的矩阵中的所有数的和。
现在设 a[i][j]a[i][j] 为第 ii 行第 jj 列的数，s[i][j]s[i][j] 为 (1,1)(1,1) 至 (i,j)(i,j) 的矩阵中的所有数的和,那么：
s[x][y]=a[x][y]+s[x−1][y]+s[x][y−1]−s[x−1][y−1]s[x][y]=a[x][y]+s[x-1][y]+s[x][y-1]-s[x-1][y-1]。
利用容斥原理可以理解上式。

二维差分

二维差分 其实也同 一维差分一样，是“反向前缀和”。
同样 一维差分一样需要先用时间复杂度为 O(n2)O(n^2) 的预处理。设预处理后的数组为 cc。
如果我们要将一个二维数组的 (x,y)(x,y) 至 (z,s)(z,s) 矩阵中的每一个数加 11 只需 44 步：
CPP
c[x][y]++;
c[x][s+1]--;
c[z+1][y]--;
c[z+1][s+1]++;
现在都知道该如何做了吧！

代码

CPP
#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&x){
	x=0;char c;int sign=1;
	do{c=getchar_unlocked();if(c=='-') sign=-1;} while(!isdigit(c));
	do{x=x*10+c-'0';c=getchar_unlocked();}while(isdigit(c));
	x*=sign;
}
int n,m;
int c[5050][5050];
int x,y,z,s;
long long ans;
int main(){
    read(n),read(m);
    for(int i=1;i<=m;i++){
        read(x),read(y),read(z),read(s);
        c[x][y]++;
        c[x][s+1]--;
        c[z+1][y]--;
        c[z+1][s+1]++;
        //差分处理
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
        	c[i][j]=c[i-1][j]+c[i][j-1]-c[i-1][j-1]+c[i][j];//前缀和处理
        	ans+=(i+j)^c[i][j];//计算答案
		}
    }
    cout<<ans;
    return 0;
}
这道题跟P3397 地毯 题干完全一样，只是数据增强与输出不同。可以复习巩固关于 前缀和 与 差分 的基础知识，也值得一做。

评论

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

正在加载评论...