P3397 地毯

题目链接https://www.luogu.com.cn/problem/P3397

题目数据很水，但是差分的模版题

方法一：模拟

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, m;
 4 int sx, sy, ex, ey;
 5 int a[1005][1005];
 6 int main()
 7 {
 8     cin>>n>>m;
 9     while(m--){//此处3重循环O（n^3）居然过了,说明数据很水
10         cin>>sx>>sy>>ex>>ey;
11         for(int i=sx; i<=ex; i++)
12             for(int j=sy; j<=ey; j++)
13                 a[i][j]+=1;
14     }
15     for(int i=1; i<=n; i++){
16         for(int j=1; j<=n; j++)
17             cout<<a[i][j]<<" ";
18         cout<<endl;
19     }
20             
21     return 0;
22  }

方法二：差分

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N =1010;
 4 int a[N][N],b[N][N];
 5 int n,m,q;
 6 int main()
 7 {
 8     scanf("%d%d",&n,&m);
 9     for(int i=1;i<=n;i++)
10         for(int j=1;j<=n;j++)
11         {
12             b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
13         }
14     while(m--)
15     {
16         int x1,y1,x2,y2;
17         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
18         b[x1][y1]+=1;
19         b[x2+1][y1]-=1;
20         b[x1][y2+1]-=1;
21         b[x2+1][y2+1]+=1;
22     }
23     for(int i=1;i<=n;i++)
24     {
25         for(int j=1;j<=n;j++)
26         {
27             a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
28             printf("%d ",a[i][j]);
29         }
30         printf("
");
31     }
32     return 0;
33 }

不讨论该题数据水的程度，一起来复习一下前缀和和差分https://www.cnblogs.com/ninedream/p/11537576.html