洛谷P3397 地毯

洛谷P3397 地毯
二维差分
与一维差分类似
每次修改相当于只要修改4个地方就可以了
然后将差分数组来一次前缀和就能做好了

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iostream>
 8 #include <iomanip>
 9 using namespace std ; 
10 
11 const int maxn = 1011 ; 
12 int n,m,sx,sy,tx,ty ; 
13 int d[maxn][maxn],a[maxn][maxn] ; 
14 
15 inline int read()
16 {
17     char ch = getchar() ; 
18     int f = 1 , x = 0 ; 
19     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 
20     while(ch>='0'&&ch<='9') { x = x*10+ch-48 ; ch = getchar() ;   } 
21     return x*f ; 
22 }
23 
24 inline void write(int x) 
25 {
26     if(x<0) x = -x ,putchar('-') ; 
27     if(x>9) write(x/10) ; 
28     putchar(x%10+48) ; 
29 }
30 
31 int main() 
32 {
33     n = read() ; m = read() ; 
34     for(int i=1;i<=m;i++) 
35     {
36         sx = read() ; sy = read() ; tx = read() ; ty = read() ; 
37         d[sx][sy]++; d[sx][ty+1]--; d[tx+1][sy]-- ; d[tx+1][ty+1]++ ; 
38     }
39     for(int i=1;i<=n;i++) 
40         for(int j=1;j<=n;j++) 
41             d[i][j] = d[i][j] + d[i][j-1] + d[i-1][j] - d[i-1][j-1] ; 
42     for(int i=1;i<=n;i++) 
43     {
44         for(int j=1;j<=n;j++) 
45             write( d[ i ][ j ] ),putchar(' ') ; 
46         puts("") ;  
47     }
48     return 0 ; 
49 }