洛谷 P3397 地毯 刷题笔记 二维差分矩阵

P3397 地毯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

方法1 欺负数据小? 暴力水过

#include<iostream>
using namespace std;
const int N=1010;
int a[N][N];
int main(){
?? ?int n,m;
?? ?cin>>n>>m;
?? ?for(int i=0;i<m;i++){
?? ??? ?int x1,y1,x2,y2;
?? ??? ?cin>>x1>>y1>>x2>>y2;
?? ??? ?for(int q=x1;q<=x2;q++){
?? ??? ??? ?for(int w=y1;w<=y2;w++){
?? ??? ??? ??? ?a[q][w]++;
?? ??? ??? ?}
?? ??? ?}?
?? ?}
?? ?for(int i=1;i<=n;i++){
?? ??? ?for(int j=1;j<=n;j++){
?? ??? ??? ?cout<<a[i][j]<<' ';
?? ??? ?}
?? ??? ?cout<<endl;
?? ?}
?? ?
?? ?
?? ?return 0;
}

方法2?

前缀和 二维数组差分?

不会差分的建议先去看看一维数组的差分

洛谷 P2367 语文成绩 刷题笔记-CSDN博客

#include<iostream>
using namespace std;
const int N=1010;
int a[N][N],b[N][N];
void add(int x1,int y1,int x2,int y2,int x){
?? ??
?? ?b[x1][y1]+=x;
?? ?b[x1][y2+1]-=x;
?? ?b[x2+1][y1]-=x;
?? ?b[x2+1][y2+1]+=x;
?? ?
}
int n,m;
int main(){
?? ?cin>>n>>m;
?? ?for(int i=0;i<m;i++){
?? ??? ?int a,b,c,d;
?? ??? ?cin>>a>>b>>c>>d;
?? ??? ?add(a,b,c,d,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]+b[i][j];
?? ??? ??? ?//扫描缓存池 计算前缀和 ?

????????//看不懂缓存池的先去看一维数组差分

????????//上面提到了
?? ??? ?}
?? ?}
?? ?for(int i=1;i<=n;i++){
?? ??? ?for(int j=1;j<=n;j++){
?? ??? ??? ?cout<<a[i][j]<<' ';
?? ??? ?}
?? ??? ?cout<<endl;
?? ?}
?? ?return 0;
}

add函数推导

a数组是b数组的前缀和数组，对b数组的b[i][j]的修改，会影响到a数组中从a[i][j]及往后的每一个数。

二维前缀和推导