#C240926A. 矩阵(啊)

网址（Website）

题目详情 - 矩阵(啊) - Super

题解 - 矩阵(啊) - Super

题解（Solution）

$\qquad$暴力枚举行，对于每个地方双指针，固定左区间 $k$ ，令 $l,r$ 分别表示满足条件的最小的右端点和最大的右端点，注意要保证 $l,r$ 大于左区间 $k$ 。

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 101234;
const int M = 50;
bool ST;

int n,m,lx,rx,ans;
int c[M][N];

inline int ask(int x1,int y1,int x2,int y2){
	return c[x2][y2] - c[x1-1][y2] - c[x2][y1-1] + c[x1-1][y1-1];
}

void Solve(){
	For(i,1,n) For(j,1,m) c[i][j] += c[i-1][j] + c[i][j-1] - c[i-1][j-1];
	
	For(i,1,n) For(j,i,n){
		int l = 1, r = 0;
		For(k,1,m){
			while(l<=m && ask(i,k,j,l)<lx) l++;
			while(r<=m && ask(i,k,j,r)<=rx) r++;
			l = max(l,k), r = max(r,k);//这一行是重点
			ans += r-l;
		}
	}
}

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	cin>>n>>m;int Tim = clock();
	For(i,1,n){
		char s[N];cin>>(s+1);
		For(j,1,m) c[i][j] = s[j]=='1';
	}cin>>lx>>rx;
	Solve(),cout<<ans<<'\n'; 
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}