题意，给出一个n行m列的矩阵
里面元素是0或者1
给出q个询问
a,b,c,d
求(a,b)到(c,d)有多少个由0组成的矩形
我们定义
对一个矩形来说
dp[a][b][c][d]=dp[a][b][c][d-1]+dp[a][b][c-1][d]-dp[a][b][c-1][d-1]+包括右下角（当前点）的矩形;
重点就在包括右下角（当前点c,d）的矩形。怎样计算这个
我们能够暴力扫描。须要nm的复杂度。乘上原有复杂度
也能够用一个VECTOR来记录1的位置。对我们扫描到的行，二分查找G[该行]中1的位置（在第b列到第d列间第一个1），然后依据相对位置再来计算，最坏查找
也能够状压整张图
我们要知道的是b列到d列中1的情况，我们把代表该行状态的数s先左位移再右位移到仅仅剩b列到d列的状态
然后作运算s&(-s)返回第一个1的位置比方。假设s是0101000,则返回8
为什么能这样？来看下是怎么回事
还是以s=0101000为例
负数即正数的补码，-s即是1010111+1=1011000
0101000
1011000 &
0001000
可是这里
会返回2^40
可是没关系。我们对返回的数模997(经測验没有地址冲突)
这样就能够把它丢到表里
vis[2^1]=1
vis[2^2]=2
vis[2^3]=3...
vis[2^40]=40
这样就能够得到当前行中b到d列里从右往左第一个1的相对于第d列的位置
算下复杂度，全是几个O(1)的操作，大致为O(1)
说下我认为最厉害最省事的方法
CF上最短size的代码
是这么做的
记录每一个格子距离上一个1的距离d[i][j]
在找包括右下角（当前点c,d）的矩形的时候，我们取adder=min(记录数d[i][d],adder)(adder一開始是d-b+1)，每次加上这个adder。从c行到a行(d[c][d]~d[a][d]),一直维护这个adder
O(1)且很方便
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
int g[55][55];
int num[55][55];
int dp[55][55][55][55];
int main(){
#ifndef ONLINE_JUDGE
freopen("/home/rainto96/in.txt","r",stdin);
#endif
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%1d",&g[i][j]);
num[i][j]=num[i][j-1]+1;
if(g[i][j]==1)
num[i][j]=0;
}
for(int a=1;a<=n;a++)
for(int b=1;b<=m;b++)
for(int c=a;c<=n;c++)
for(int d=b;d<=m;d++){
int& now=dp[a][b][c][d]=dp[a][b][c][d-1]+dp[a][b][c-1][d]-dp[a][b][c-1][d-1];
int add=d-b+1;
for(int i=c;i>=a;i--){
add=min(add,num[i][d]);
now+=add;
}
}
for(int i=1;i<=q;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
cout<<dp[a][b][c][d]<<endl;
}
}