二维前缀和、差分习题集

https://blog.csdn.net/K_R_forever/article/details/81775899

先给p个矩形，再给q个矩形，q个矩形中若能被p个矩形所在区域包含则YES，否则NO。转化为二维差分问题。

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 #define ls(rt) (rt<<1)
24 #define rs(rt) (rt<<1|1)
25 #define lowbit(x) (x&(-x))
26 using namespace std;
27 const int MAXN=1e7+5;
28 int a[MAXN];
29 int n,m,p,q;
30 int pos(int x,int y)
31 {
32     if(x<1||y<1||x>n||y>m) return 0;
33     return (x-1)*m+y;
34 }
35 void add(int x,int y,int k)
36 {
37     if(!pos(x,y)) return;
38     a[pos(x,y)]+=k;
39 }
40 int query(int x,int y)
41 {
42     if(!pos(x,y)) return 0;
43     return a[pos(x,y)];
44 }
45 int read()
46 {
47     int s=1,x=0;
48     char ch=getchar();
49     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
50     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
51     return x*s;
52 }
53 int main()
54 {
55     while(~scanf("%d%d",&n,&m))
56     {
57         mem(a,0);
58         p=read();
59         for(int i=1;i<=p;++i)
60         {
61             int x1=read(),y1=read(),x2=read(),y2=read();
62             add(x1,y1,1);add(x2+1,y2+1,1);
63             add(x2+1,y1,-1);add(x1,y2+1,-1);
64         }
65         
66         //因为a数组初始化为0，计算后a[x,y]为二维前缀和，
67         //即代表p区域的个数 
68         for(int i=1;i<=n;++i)
69         for(int j=1;j<=m;++j)
70         a[pos(i,j)]+=query(i,j-1)+query(i-1,j)-query(i-1,j-1);
71         
72         //a[x,y]只要大于1，说明有p区域 ，赋值为1 
73         for(int i=1;i<=n;++i)
74         for(int j=1;j<=m;++j)
75         a[pos(i,j)]=a[pos(i,j)]>0;
76         
77         //再计算一遍前缀和，a[x,y]代表[0,0]到[x,y]p区域标记的大小 
78         for(int i=1;i<=n;++i)
79         for(int j=1;j<=m;++j)
80         a[pos(i,j)]+=query(i,j-1)+query(i-1,j)-query(i-1,j-1);
81         
82         q=read();
83         for(int i=1;i<=q;++i)
84         {
85             int x1=read(),y1=read(),x2=read(),y2=read();
86             int A=(x2-x1+1)*(y2-y1+1);
87             int B=query(x2,y2)+query(x1-1,y1-1)-query(x2,y1-1)-query(x1-1,y2);
88             //要完全覆盖 
89             if(A==B) puts("YES");
90             else puts("NO");
91         }
92     }
93     return 0;
94 }

View Code

也可以用二维数组：https://blog.csdn.net/yiqzq/article/details/89422474

2、CF White Lines

给个n*n的矩形，元素非'W'即'B'，将k*k的小矩形中的元素都变为'W'，问最大的白线数目（即一行或一列都是'W'）

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 #define ls(rt) (rt<<1)
24 #define rs(rt) (rt<<1|1)
25 #define lowbit(x) (x&(-x))
26 using namespace std;
27 const int MAXN=2e3+5;
28 int sum[MAXN][MAXN],n,k;
29 char paint[MAXN][MAXN];
30 int add[MAXN][MAXN];
31 int read()
32 {
33     int s=1,x=0;
34     char ch=getchar();
35     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
36     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
37     return x*s;
38 }
39 int main()
40 {
41     n=read(),k=read();
42     for(int i=1;i<=n;++i)
43     cin>>paint[i]+1;
44 
45     for(int i=1;i<=n;++i)//处理每一行对sum[x][y]的贡献 
46     {
47         int L=0,R=0;//每一行最左的B和最右的B的下标 
48         for(int j=1;j<=n;++j)
49         {
50             if(paint[i][j]=='B')
51             {
52                 if(L==0) L=j,R=j;
53                 else R=j;
54             }
55         }
56         if(L==0) {add[1][1]++;continue;}//这一行全白，+1
57         if(R-L+1>k) continue;//这一行怎么擦也不能全白
58         //二维差分相关操作 ，前缀和修改操作 
59         int x1=max(1,i-k+1),y1=max(1,R-k+1),x2=i,y2=L;
60         add[x1][y1]++,add[x2+1][y1]--,add[x1][y2+1]--,add[x2+1][y2+1]++; 
61     }
62     
63     for(int j=1;j<=n;++j)
64     {
65         int U=0,D=0;//每一列最上的B和最下的B的下标 
66         for(int i=1;i<=n;++i)
67         {
68             if(paint[i][j]=='B')
69             {
70                 if(U==0) U=i,D=i;
71                 else D=i;
72             }
73         }
74         if(D==0) {add[1][1]++;continue;}//这一列全白，+1
75         if(D-U+1>k) continue; //这一列怎么擦也不能全白
76         //
77         int x1=max(1,D-k+1),y1=max(1,j-k+1),x2=U,y2=j;
78         add[x1][y1]++,add[x2+1][y1]--,add[x1][y2+1]--,add[x2+1][y2+1]++;
79     }
80     
81     int ans=0;
82     for(int i=1;i<=n;++i)
83     for(int j=1;j<=n;++j)
84     {
85         sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+add[i][j];//计算二维前缀和 
86         ans=max(ans,sum[i][j]);
87     }
88     cout<<ans<<endl;
89 }

View Code

可参考：https://blog.csdn.net/qq_40889820/article/details/99430740