链接：https://www.luogu.com.cn/problem/CF364E
题目描述：你有一个\(n*m\)的\(01\)矩阵，现在询问在这其中有多少个子矩阵满足包含\(k\)个\(1\)，即和为\(k\)。
题解：考虑枚举一个矩形在行坐标的左边界与右边界，那么原问题可以转化为一维问题，只需统计有多少个区间内部元素和恰好为\(k\)，可以线性扫描解决，但这样的复杂度是\(O(m^2n)\)的。
考虑扫描线，枚举左边界扫右边界，每次将每一个右边界的\(1\)加入，每一次对一行\(+1\)，我们发现一个\(1\)只有其到左边界的\(1\)小于等于\(<=k+1\)时才可能产生贡献。那么只要扫有贡献的\(1\)，合法个数是\(O(nk)\)级别的。对于每一个\(1\)，其增量是加入后跨过这一行的内部元素和恰好为\(k\)的区间个数\(-\)加入前的，那么可以用倍增树状数组求出合法区间个数，复杂度\(O(nmk^2logk)\)，但常数太大无法通过。
由于进一步优化要\(O(1)\)查询前驱后继，考虑倒序扫描线，用链表维护，那么这样由于每一次加入一个点是复杂度是\(O(k)\)的，所以复杂度\(O(nmk^2)\)。
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#define int long long
#define RG register
#define N 3000
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
vector<int>T[N+1];
long long n,m,k,leng,ans,delta,cnt[N+1],a[N+1][N+1],nxt[N+1][N+1],top[N+1][N+1],length[N+1],color[7*N+1];
int pv[7*N+1],nt[7*N+1],dque[N+1],f[N+1],l[N+1],r[N+1],Top;
long long A[N+1],B[N+1];
inline void solve(int x,int d,int op)
{
int p1=x,p2=x,c;
for (RG int q=0;q<=k;++q) A[q]=B[q]=0;
while (pv[p1]!=0&&color[pv[p1]]==color[p1]) p1=pv[p1];
if (op)
{
while (nt[p2]!=leng+1&&color[nt[p2]]==color[p2]) p2=nt[p2];
}
c=p2-p1+1;
if (op==2) c=0;
for (RG int q=0;q<=k-c&&p1!=0;++q) A[q]=color[p1]-color[pv[p1]],p1=pv[p1];
for (RG int q=0;q<=k-c&&p2!=leng+1;++q) B[q]=color[nt[p2]]-color[p2],p2=nt[p2];
if (op)
{
for (RG int q=0;q<=k-c;++q) delta+=d*A[q]*B[k-c-q];
}
else if (k>=c) delta+=d*A[k-c]*B[0];
return;
}
signed main()
{
char x;
n=read(),m=read(),k=read();
for (RG int i=1;i<=n;++i)
for (RG int j=1;j<=m;++j)
cin>>x,a[i][j]=(x=='1');
for (RG int i=1;i<=n;++i)
for (RG int j=m;j>=1;--j)
{
if (a[i][j]==1) top[i][++length[i]]=j;
nxt[i][j]=length[i];
}
for (RG int i=1;i<=m;++i)
{
if (k==0)
{
Top=0;
dque[Top=0]=0;
for (RG int j=1;j<=n;++j)
{
if (nxt[j][i]==0) f[j]=m-i+1;
else f[j]=top[j][nxt[j][i]]-i;
while (Top>0&&f[dque[Top]]>=f[j]) Top--;
l[j]=j-dque[Top],dque[++Top]=j;
}
dque[Top=0]=n+1;
for (RG int j=n;j>=1;--j)
{
while (Top>0&&f[dque[Top]]>f[j]) Top--;
r[j]=dque[Top]-j,dque[++Top]=j;
}
for (RG int j=1;j<=n;++j) ans+=l[j]*r[j]*f[j];
continue;
}
delta=0,leng=0;
for (RG int j=0;j<=m;++j) T[j].clear();
for (RG int j=1;j<=n;++j)
for (RG int t=max(1ll,nxt[j][i]-k);t<=nxt[j][i];++t)
T[top[j][t]].push_back(++leng),color[leng]=j;
for (RG int j=1;j<=leng;++j) pv[j]=j-1,nt[j]=j+1;
color[leng+1]=n+1;
for (RG int j=1;j<=leng;++j) solve(j,1,0);
ans+=delta;
for (RG int j=m;j>=i+1;--j)
{
for (int t=0;t<T[j].size();++t)
{
solve(T[j][t],-1,1),nt[pv[T[j][t]]]=nt[T[j][t]],pv[nt[T[j][t]]]=pv[T[j][t]];
if (color[pv[T[j][t]]]==color[T[j][t]]) solve(pv[T[j][t]],1,1);
else if (color[nt[T[j][t]]]==color[T[j][t]]) solve(nt[T[j][t]],1,1);
else solve(T[j][t],1,2);
}
ans+=delta;
}
}
printf("%lld\n",ans);
return 0;
}