20200411 T2 画画（数边框涂色正方形个数）

题目描述：

有一个熊孩子在方格纸上画了 $m$m 条水平或竖直的线段（方格纸的坐标范围为$[0,n]$[0,n]）。现在请统计这些线段组成了 多少个正方形(这些正方形可以重叠，而且边长任意)。
$n\le2000,m\le2*10^6$n≤2000,m≤2∗106
数据保证不存在"平行且有重合部分(包括线段端点的重合)"的两条线段。

题目分析：

如果坐标系中的一条边被线段覆盖，则称其被“染色”了。
题目即求有多少个正方形满足它的边框都被染色了。

按坐标系方向，求出每个点向左能延伸(被覆盖)的最长长度 $L[i][j]$L[i][j]，向下延伸的最长长度 $D[i][j]$D[i][j]
开 $2n$2n 个长度为 $n$n 的bitset $A_{l,i},B_{l,i}$Al,i​,Bl,i​，$A_{l,i}[j]=1$Al,i​[j]=1表示$L[i][j]\ge l$L[i][j]≥l， $B_{l,i}[j]=1$Bl,i​[j]=1表示$D[i][j]\ge l$D[i][j]≥l
那么枚举正方形边长 $l$l 和正方形的右边界 $i$i，满足条件的正方形个数就是 $A_{l,i}\&(A_{l,i}<<l)\&B_{l,i}\&B_{l,i-l}$Al,i​&(Al,i​<<l)&Bl,i​&Bl,i−l​中 1 的个数。
这样做的时间和空间复杂度都是 $O({n^3\over w})$O(wn3​)的，会MLE。

可以按照 $l$l 由大到小的顺序进行计算，每次加入$L[i][j]=l$L[i][j]=l和$D[i][j]=l$D[i][j]=l的点，这样就可以省去bitset的第一维，空间复杂度降为$O({n^2\over w})$O(wn2​)

（往下翻还有拓展）

Code：

#include<bits/stdc++.h>
#define maxn 2005
using namespace std;
char cb[1<<20],*cs,*ct;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<20,stdin),cs==ct)?0:*cs++)
inline void read(int &a){
	char c;while(!isdigit(c=getc()));
	for(a=c-'0';isdigit(c=getc());a=a*10+c-'0');
}
typedef pair<int,int> pii;
int n,m;
bool c[maxn][maxn][2];
bitset<maxn>A[maxn],B[maxn];
vector<pii>q[maxn][2];
long long ans;
int main()
{
	freopen("draw.in","r",stdin);
	freopen("draw.out","w",stdout);
	read(n),read(m);
	for(int i=1,x,y,l,r;i<=m;i++){
		read(x),read(y),read(l),read(r);
		for(int j=x+1;j<=l;j++) c[j][y][0]=c[j][r][0]=1;
		for(int j=y+1;j<=r;j++) c[x][j][1]=c[l][j][1]=1;
	}
	for(int j=0;j<=n;j++)
		for(int i=1,pre=0,now;i<=n;i++,pre=now)
			q[now=(c[i][j][0]?pre+1:0)][0].push_back(pii(i,j));
	for(int i=0;i<=n;i++)
		for(int j=1,pre=0,now;j<=n;j++,pre=now)
			q[now=(c[i][j][1]?pre+1:0)][1].push_back(pii(i,j));
	for(int l=n;l>=1;l--){
		pii t;
		for(int i=0,lim=q[l][0].size();i<lim;i++) t=q[l][0][i],A[t.first][t.second]=1;
		for(int i=0,lim=q[l][1].size();i<lim;i++) t=q[l][1][i],B[t.first][t.second]=1;
		for(int i=l;i<=n;i++)
			ans+=(A[i]&(A[i]<<l)&B[i]&B[i-l]).count();
	}
	printf("%lld\n",ans);
}

拓展：矩形

这个bitset的做法不仅可以做正方形，还可以做矩形，比如有 $m$m 个询问底边为 $a_i$ai​ 侧边为 $b_i$bi​的矩形个数。

预处理所有长度的bitset的做法依然适用，想办法优化空间：
如果按照侧边长度由大到小计算，$B$B的空间压下来了，但是$A$A仍然需要预处理。
沿用$ST$ST表的想法，预处理$logn$logn个bitset $A_{k,i}$Ak,i​，$A_{k,i}[j]=1$Ak,i​[j]=1表示$L[i][j]\ge 2^k$L[i][j]≥2k，那么对于一个询问 $a,b$a,b，枚举矩形右边界的位置 $i$i，记$k=\lfloor log_2a\rfloor$k=⌊log2​a⌋，$A'=A_{k,i}\&A_{k,i-l+2^k}$A′=Ak,i​&Ak,i−l+2k​
答案即为：
$A'\&(A'<<b)\&B_i\&B_{i-l}$A′&(A′<<b)&Bi​&Bi−l​中 1 的个数。
时间复杂度 $O({n^2log+n^2m\over w})$O(wn2log+n2m​)，空间复杂度为 $O({n^2log+n^2\over w})$O(wn2log+n2​)

正方形更快的解法：

对于求正方形有更快的解法，由于正方形的左下角和右上角的横纵坐标之差是个定值，所以可以分成一条条斜线来做。
预处理出每个点向上下左右分别能延伸的长度，即为$U,D,L,R$U,D,L,R
枚举横纵坐标之差$d$d，再枚举$x$x，令$y=x+d$y=x+d，则$(x,y)$(x,y)作为正方形的左下角，它的左边和下边能够和$x'\in(x,x+\min(U[x][y],R[x][y])]$x′∈(x,x+min(U[x][y],R[x][y])]的右上角相接，它作为正方形的右上角，它的上边和右边能够和$x'\in[x-\min(D[x][y],L[x][y]),x)$x′∈[x−min(D[x][y],L[x][y]),x)相接。
相当于枚举到$x$x时，在当前点+1，如果这个点是某个$x=x'+\min(U[x'][y'],R[x'][y'])+1$x=x′+min(U[x′][y′],R[x′][y′])+1，则在当前点-1，查询$[x-\min(D[x][y],L[x][y]),x)$[x−min(D[x][y],L[x][y]),x)区间的和就是以这个点作为右上角的正方形个数。
时间复杂度$O(n^2logn)$O(n2logn)，空间复杂度$O(n^2)$O(n2)