题解 P1950 【长方形】

## 题目大意 询问在一个 $n\times m$ 的长方形中，所有不包含记号的矩形的总数。 ## 题解 题解区里大多都是 $\mathcal O(n^2)$ 的单调栈写法。但单调栈其实并不怎么好想……这里提供一个 $\mathcal O(n^2 \log n)$ 的比较容易想到的线段树解法吧。 考虑从上到下，从左到右枚举矩阵的**右下角**。不妨设当前处理到 $(i,j)$ ，我们如何从它左侧的一个点 $(i,j-1)$ 转移过来呢？ 显然，右下角为 $(i,j)$ 的矩形，它的最大高度为 $(i,j)$ 到上方最近的标记（或者边界）的距离，不妨记为 $F_{i,j}$ 。 $F_{i,j}$ 比较容易求得。 $$F_{i,j}=\begin{cases} 0 & (i,j) \text{ 就是标记 } \cr F_{i-1,j}+1 & (i,j) \text{ 不是标记 }\end{cases}$$ 我们能够发现，**右下角为 $(i,j)$ ，高度为 $h$ 的矩阵的方案数，就是 右下角为 $(i,j-1)$ ，高度为 $h$ 的矩阵的方案数 $+1$**。因为，每个高度为 $h$ 的方案，相当于一根高度为 $h$ 的柱子，再从左侧拼接了一个高度为 $h$ 的矩形。考虑维护不同高度的矩阵的方案数。我们需要以下三种操作： - 清空高度为 $(F_{i,j}+1)\sim +\infty$ 的矩阵的方案数。 - 将高度为 $1 \sim F_{i,j}$ 的矩阵的方案数全部 $+1$ 。 - 求高度为 $1 \sim F_{i,j}$ 的矩阵的方案数的和。 我们可以用线段树实现这三个操作。当然，$+\infty$ 只要取 $n+1$ 就行了。 因此总复杂度为 $\mathcal O(n^2\log n)$ 。由于 $n\le 10^3$ ，因此能够通过本题。 ## 参考代码 ```cpp #include<bits/stdc++.h> #define up(l,r,i) for(int i=l;i<=r;i++) #define dn(l,r,i) for(int i=l;i>=r;i--) using namespace std; typedef long long LL; const int INF =2147483647; int qread(){ int w=1,c,ret; while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0'; while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0'; return ret*w; } int readln(char *s){ int len=0,c; while((c=getchar())==10||c==13); if(c==EOF) return -1; s[len++]=c; while((c=getchar())!=10&&c!=13&&c!=EOF) s[len++]=c; s[len]=0; return len; } #define lc(t) (t<<1) #define rc(t) (t<<1|1) const int MAXN =1e3+3,SIZ=MAXN*4; int W[SIZ],B[SIZ]; bool A[SIZ]; void upd(int t,int a,int b){ if(a==b) return; int mid=a+b>>1; if(A[t]) A[lc(t)]=A[rc(t)]=true,B[lc(t)]=B[rc(t)]=W[lc(t)]=W[rc(t)]=0; if(B[t]){ B[lc(t)]+=B[t],B[rc(t)]+=B[t]; W[lc(t)]+=(mid-a+1)*B[t],W[rc(t)]+=(b-mid)*B[t]; } A[t]=B[t]=0,W[t]=W[lc(t)]+W[rc(t)]; } void add(int t,int l,int r,int a,int b){ if(l<=a&&b<=r){W[t]+=b-a+1,++B[t];return;} int mid=a+b>>1; upd(t,a,b); if(l<=mid) add(lc(t),l,r,a,mid ); if(r> mid) add(rc(t),l,r,mid+1,b); W[t]=W[lc(t)]+W[rc(t)]; } void clc(int t,int l,int r,int a,int b){ if(l<=a&&b<=r){W[t]=0,A[t]=true,B[t]=0;return;} int mid=a+b>>1; upd(t,a,b); if(l<=mid) clc(lc(t),l,r,a,mid ); if(r> mid) clc(rc(t),l,r,mid+1,b); W[t]=W[lc(t)]+W[rc(t)]; } void qry(int t,int l,int r,int a,int b,int &o){ if(l<=a&&b<=r){o+=W[t]; return;} int mid=a+b>>1; upd(t,a,b); if(l<=mid) qry(lc(t),l,r,a,mid ,o); if(r> mid) qry(rc(t),l,r,mid+1,b,o); } int n,m,F[MAXN][MAXN],v; LL ans; char S[MAXN][MAXN]; int main(){ n=qread(),m=qread(),v=n+1,memset(S[0],'*',sizeof(S[0])); up(1,n,i) readln(S[i]+1); up(0,n,i) up(1,m,j) if(S[i][j]=='*') F[i][j]=i; else F[i][j]=F[i-1][j]; up(1,n,i){ int x=0; clc(1,1,v,1,v); up(1,m,j){ if(S[i][j]=='*'){clc(1,1,v,1,v);continue;} int w=i-F[i][j],t=0; clc(1,w+1,v,1,v),add(1,1,w,1,v),qry(1,1,w,1,v,t); ans+=1ll*t; } } printf("%lld\n",ans); return 0; } ```