http://codeforces.com/problemset/problem/372/B
题意:每次给出一个区间，求里面有多少个矩形
思路:预处理，sum[i][j][k][l]代表以k,l为右下角，左上角不超过i,j有多少矩形，然后询问的时候枚举右下角就可以了
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #include<cstring> 5 #include<iostream> 6 int n,m,T; 7 int sum[45][45][45][45],l[45][45]; 8 char s[2005]; 9 int read(){ 10 int t=0,f=1;char ch=getchar(); 11 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} 12 while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} 13 return t*f; 14 } 15 void init(){ 16 for (int i=1;i<=n;i++){ 17 scanf("%s",s+1); 18 for (int j=1;j<=m;j++){ 19 if (s[j]=='1') continue; 20 if (s[j-1]=='0') l[i][j]=l[i][j-1]+1; 21 else l[i][j]=1; 22 } 23 } 24 for (int i=1;i<=n;i++) 25 for (int j=1;j<=m;j++) 26 for (int k=i;k<=n;k++) 27 for (int L=j;L<=m;L++){ 28 int tmp=1<<29; 29 int ss=0; 30 for (int x=k;x>=i;x--){ 31 int ll=std::min(L-j+1,l[x][L]); 32 tmp=std::min(tmp,ll); 33 ss+=tmp; 34 } 35 sum[i][j][k][L]=ss; 36 } 37 } 38 int main(){ 39 n=read();m=read();T=read(); 40 init(); 41 while (T--){ 42 int x1=read(),y1=read(),x2=read(),y2=read(),ans=0; 43 for (int i=x1;i<=x2;i++) 44 for (int j=y1;j<=y2;j++) 45 ans+=sum[x1][y1][i][j]; 46 printf("%d ",ans); 47 } 48 return 0; 49 }