CF-372B Counting Rectangles is Fun

题意

给定一个 n×mn\times m 的 0101 矩阵, qq 次询问, 每次询问指定一个子矩形, 求该子矩形种有多少个只包含 00 的子矩阵.

矩阵从上到下编号 [1,n][1,n], 从左到右编号 [1,m][1,m]

1≤n,m≤40,1≤q≤3×1051\le n,m\le 40,1\le q\le 3\times 10^5

题解

n,m≤40n,m\le 40 ，qq 却很大，可以想到应该是一个 O(n2m2)O(n^2m^2) 的预处理 + O(1)O(1) 的查询。

首先，判断 (a,b),(c,d)(a,b),(c,d)（左上角和右下角）的矩形是否全零可以 O(1)O(1) ，记 f[L][R][l][r]f[L][R][l][r] 表示 (L,l),(R,r)(L,l),(R,r) 是否为全零矩阵 ，如果 L>RL>R 或 l>rl>r 就是 00，对于一组询问 (a,b),(c,d)(a,b),(c,d)

ans=∑L=ac∑R=ac∑l=bd∑r=bdf[L][R][l][r]ans=\sum_{L=a}^c\sum_{R=a}^c\sum_{l=b}^d\sum_{r=b}^d f[L][R][l][r]

这玩意显然可以前缀和，要注意一些细节，先枚举 L,RL,R ，对后面的 [l][r],b≤l,r≤d[l][r] ,b\le l,r\le d 进行二维前缀和

tmp[l][r]=∑i=1l∑j=1rf[L][R][i][j]tmp[l][r]=\sum_{i=1}^l\sum_{j=1}^r f[L][R][i][j]

f′[L][R][l][r]f'[L][R][l][r] 的定义为上边为 LL，下边为 RR ，左右边在 [l,r][l,r] 内的全零矩阵个数，显然有

f′[L][R][l][r]=tmp[m][r]−tmp[l−1][r]f'[L][R][l][r]=tmp[m][r]-tmp[l-1][r]

现在：

ans=∑L=ac∑R=acf′[L][R][b][d]ans=\sum_{L=a}^c\sum_{R=a}^c f'[L][R][b][d]

显然还可以再对 f′[L][R]f'[L][R] 前缀和，枚举 l,rl,r 对 [L][R][L][R] 前缀和：

tmp′[L][R]=∑i=1L∑j=1Rf[L][R][l][r]tmp'[L][R]=\sum_{i=1}^L\sum_{j=1}^R f[L][R][l][r]

f′′[L][R][l][r]f''[L][R][l][r] 的定义为上下边在 [L,R][L,R] 内，左右边在 [l,r][l,r] 内的全零矩阵个数，类似的：

f′′[L][R][l][r]=tmp[n][R]−tmp[L−1][R]f''[L][R][l][r]=tmp[n][R]-tmp[L-1][R]

以上预处理 O(n2m2)O(n^2m^2) ，询问 O(1)O(1) 输出 f′′[a][c][b][d]f''[a][c][b][d] 即可。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);i++) 
using namespace std;
template<typename T>
inline void red(T &x) {
    x=0;bool fg=0;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(T)(ch^48),ch=getchar();
    if(fg) x=-x;
}
const int N = 43;
int s[N][N],f[N][N][N][N],n,m,q;
// f[L][R][l][r] 行在 [L,R]，列在 [l,r] 的矩形个数
int tmp[N][N];
char str[N][N];
int cnt(int a,int b,int c,int d) {
    return (a>c||b>d)?(-1):(s[c][d]-s[c][b-1]-s[a-1][d]+s[a-1][b-1]);
}
int main() {
    red(n);red(m);red(q);
    FOR(i,1,n) {
        scanf("%s",str[i]+1);
        FOR(j,1,m) {
            s[i][j]=(str[i][j]=='1');
        }
    }
    FOR(i,1,n) FOR(j,1,m) s[i][j]+=s[i][j-1];
    FOR(i,1,n) FOR(j,1,m) s[i][j]+=s[i-1][j];
    
    FOR(L,1,n) FOR(R,L,n) {
        memset(tmp,0,sizeof(tmp));
        FOR(l,1,m) FOR(r,1,m) tmp[l][r]=(cnt(L,l,R,r)==0);
        FOR(l,1,m) FOR(r,1,m) tmp[l][r]+=tmp[l-1][r];
        FOR(l,1,m) FOR(r,1,m) tmp[l][r]+=tmp[l][r-1];   
        FOR(l,1,m) FOR(r,1,m) f[L][R][l][r]=tmp[m][r]-tmp[l-1][r];  
    }
    FOR(l,1,m) FOR(r,1,m) {
        memset(tmp,0,sizeof(tmp));
        FOR(L,1,n) FOR(R,1,n) tmp[L][R]=f[L][R][l][r];
        FOR(L,1,n) FOR(R,1,n) tmp[L][R]+=tmp[L-1][R];
        FOR(L,1,n) FOR(R,1,n) tmp[L][R]+=tmp[L][R-1];
        FOR(L,1,n) FOR(R,1,n) f[L][R][l][r]=tmp[n][R]-tmp[L-1][R];
    }
    while(q--) {
        int a,b,c,d;red(a);red(b);red(c);red(d);
        printf("%d\n",f[a][c][b][d]);
    }   
    return 0;
}