题意:每次给出一个区间，求里面有多少个矩形

思路:预处理，sum[i][j][k][l]代表以k,l为右下角，左上角不超过i,j有多少矩形，然后询问的时候枚举右下角就可以了

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           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\n",ans);  47     }48     return 0;49 }