>
> [AHOI2014/JSOI2014]拼图
链接：https://www.luogu.com.cn/problem/P4039
题目描述:有一些长为$n$，宽为$w_{i}$的黑白色矩形，要将它们拼成一个$ntimes m$的大矩形，求大矩形中最大的全白子矩形的面积的最大值。
题解：话说我一开始只会$O(n^2m)$，不会$O(m^2n)$，尽管知道这题可以根号分治都不会做。
$ntimes m<=10^5$，这让人莫名想起CmdOI2019简单的数论题。依照那题的方法，我们可以考虑根号分治，考虑$O(n^2m)$与$O(m^2n)$两种情况。
$O(n^2m)$:可以暴力枚举行的左右端点，对于这$S$个矩形，我们可将完整的白块放在中间，两边各放两个靠右边$0$列最多的块与靠左边$0$列最多的块，这样拼是最优的。
$O(nm^2)$:记每一个点$(i,j)$离他最近的$1$的行为$up_{i,j}$，将枚举行的左右端点时换作枚举每个点，判时判左端点为$up_{i,j}+1$，右端点为$i$的情况即可。
当然，这题有个小坑：每个矩形本身的最大的全白子矩形也要统计到达答案里。
```
#include
#include
#include
#define inf 1e9
using namespace std;
int n,m,S,w[300001],lst[300001];
int p[300001],up[300001],sum[300001],T[300001],length;
long long ans;
char t;
int f(int l,int r)
{
if (l==0||r==0)
return 0;
return (l-1)*m+r;
}
int getsum(int l,int r,int l2,int r2)
{
return sum[f(r,r2)]-sum[f(l-1,r2)]-sum[f(r,l2-1)]+sum[f(l-1,l2-1)];
}
void solve(int l,int r)
{
long long res=0,ll,rr,maxr=0,maxn=0,maxr2=0,maxn2=0,mixn=0,mixn2=0;
for (int i=1;i<=S;++i)
{
if (getsum(l,r,lst[i-1]+1,lst[i])==0)
res+=w[i];
else
{
for (int j=lst[i-1]+1;j<=lst[i];++j)
if (getsum(l,r,lst[i-1]+1,j)!=0)
{
if (j-lst[i-1]-1>maxn)
{
maxn=j-lst[i-1]-1;
maxr=i;
}
else if (j-lst[i-1]-1>mixn)
mixn=j-lst[i-1]-1;
break;
}
for (int j=lst[i];j>=lst[i-1]+1;--j)
if (getsum(l,r,j,lst[i])!=0)
{
if (lst[i]-j>maxn2)
{
maxn2=lst[i]-j;
maxr2=i;
}
else if (lst[i]-j>mixn2)
mixn2=lst[i]-j;
break;
}
ll=lst[i-1]+1;
rr=-inf;
for (int j=lst[i-1]+1;j<=lst[i];++j)
{
if (getsum(l,r,j,j)==0)
rr=j;
else
{
ans=max(ans,(r-l+1)*(rr-ll+1));
ll=j+1;
}
}
}
}
if (maxr==maxr2)
ans=max(ans,(res+max(mixn2+maxn,mixn+maxn2))*(r-l+1));
else
ans=max(ans,(res+maxn+maxn2)*(r-l+1));
return;
}
void work()
{
ans=length=m=0;
scanf("%d%d",&S,&n);
for (int i=1;i<=S;++i)
{
scanf("%lld",&w[i]);
m+=w[i];
lst[i]=lst[i-1]+w[i];
for (int k=1;k<=n*w[i];++k)
{
++length;
T[length]=0;
while (T[length]!='0'&&T[length]!='1')
T[length]=getchar();
}
}
length=0;
for (int i=1;i<=S;++i)
for (int k=1;k<=n;++k)
for (int j=lst[i-1]+1;j<=lst[i];++j)
{
++length;
p[f(k,j)]=T[length]-'0';
}
int pointer;
for (int i=1;i<=m;++i)
{
pointer=0;
for (int j=1;j<=n;++j)
{
if (p[f(j,i)]==1)
pointer=j;
up[f(j,i)]=pointer;
}
}
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
sum[f(i,j)]=p[f(i,j)]+sum[f(i-1,j)]+sum[f(i,j-1)]-sum[f(i-1,j-1)];
if (n