【JZOJ A组】a

Description

给定一个n*m 的 01 矩阵，求包含[l,r]个 1 的子矩形个数。

Input

第一行，两个正整数n，m。
接下来n 行，每行一个长度为 m 的 01 串，表示给定的矩阵。接下来一行，两个自然数 l，r。

Output

第一行，一个整数代表答案。

Sample Input

见下发文件

Sample Output

见下发文件

Data Constraint

思路

考试的时候想漏了一点

因为n很小，所以我们可以在n上为所欲为。
用n^2枚举举证上下界，对于中间每一行t，维护两个值x，y，表示sum[x–t]

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=5e4+77;
int n,m,l,r;
long long a[40][maxn],sum[40][maxn],q[maxn],ans;
char s[maxn];
int main()
{
    freopen("a.in","r",stdin); freopen("a.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%s\n",s+1);
        for(int j=1; j<=m; j++)
        {
            a[i][j]=s[j]-'0'; sum[i][j]=sum[i-1][j]+a[i][j];
        }
    }
    scanf("%d%d",&l,&r);
    for(int i=1; i<=n; i++) for(int j=i; j<=n; j++)
    {
        int x=0,y=0;
        for(int k=1; k<=m; k++)
        {
            q[k]=q[k-1]+sum[j][k]-sum[i-1][k];
        }
        for(int k=1; k<=m; k++)
        {
            while(q[k]-q[x]>=l&&x<k) x++;
            while(q[k]-q[y]>r&&y<k) y++;
            ans+=1ll*x-1ll*y;
        }
    }
    printf("%lld",ans);
}