P1950

CJ_Fu · 2022-05-04 16:32:43 · 个人记录

单调栈

暴力（前缀和）O(n^4)

code:

#include<iostream>
#define For(l,r,k) for(int (k)=(l);(k)<=(r);(k)++)
using namespace std;
int a[1003][1003],b[1003][1003],ans=0;
int main(int argc, char const *argv[])
{
    int n,m;
    cin>>n>>m;
    For(1,n,i) For(1,m,j){
            char ch;
            cin>>ch;
            a[i][j]=(ch=='.'?0:1);
        }
    For(1,n,i) For(1,m,j)
        b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];//二维前缀和
    For(1,n,i) For(1,m,j) For(i,n,k) For(j,m,l)
        if(b[k][l]-b[i-1][l]-b[k][j-1]+b[i-1][j-1]==0)
                        ans++;

    cout<<ans;
    return 0;
}

悬线法 O(n^3)

code:

#include<iostream>
#include<climits>
#define int long long
using namespace std;
int h[1003][1003],n,m,ans;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            char ch;
            cin>>ch;
            if(ch=='*') h[i][j]=0;
            else h[i][j]=h[i-1][j]+1;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            int sum=0,minn=INT_MAX;
            for(int k=j;k>0;k--){
                minn=min(minn,h[i][k]);
                sum+=minn;
            }
            ans+=sum;
        }
    cout<<ans;
    return 0;
}

囧仙线段树 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 就行了。

因此总复杂度为 O(n^2\log n) 。由于 n\le 10^3 ，因此能够通过本题。

code:

#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;
}

wlzhouzhuan单调队列 O(n^2)
接下来, 我们用:

- $l_{i, j}$ 表示从 $(i, j)$ 开始第一个满足 $h_{i, l_{i, j}} \leq h(i, j)$ 的点, 如果不存在, 令 $l_{i, j}=0$ 。 - $r_{i, j}$ 表示从 $(i, j)$ 开始第一个满足 $h_{i, r_{i, j}} \leq h(i, j)$ 的点, 如果不存在, 令 $r_{i, j}=m+1$ 。

那么, 对于 (i, j) 为矩形底的贡献, 就是 \overline{\text{val}}=\left(j-l_{i, j}\right) \times\left(r_{i, j}-j\right) \times h_{i, j } 。

考虑一下, 这样做如何保证答案不重不漏。

不重: 当且仅当在同一行存在两个数 l_{i, j_{1}}=l_{i, j_{2}} 并且 r_{i, j_{1}}=r_{i, j_{2}} 的时候, 才有可能算重矩形。但是这种情况是不存在的, 因为 l_{i, j} 满足了左边第一个小于等于的，右边第一个小于的，显然无法构造出这种情况。

不漏: 对于一个矩形, 总有一个 l_{i, j}, r_{i, j} 能框住一个矩形的两边, 故这个矩形一定能被计算到。

我们可以通过一个单调栈来计算 l_{i, j} 和 r_{i, j} , 复杂度 O\left(n^{2}\right) 。

但是我写代码的时候 ** 了 , 所以用了一个单调队列来维护, 但本质上是一样的。

code:

#include <bits/stdc++.h>
using namespace std;

#define rint register int
const int N = 1005;
bool a[N][N];
int h[N][N], l[N][N], r[N][N], n, m;

deque <int> deq;

void push_l(int i, int j) {
  while (!deq.empty() && h[i][deq.back()] > h[i][j]) r[i][deq.back()] = j, deq.pop_back();
  deq.push_back(j);
}
void push_r(int i, int j) {
  while (!deq.empty() && h[i][deq.back()] >= h[i][j]) l[i][deq.back()] = j, deq.pop_back();
  deq.push_back(j);
}

int main() {
  scanf("%d%d", &n, &m);
  for (rint i = 1; i <= n; i++) {
    for (rint j = 1; j <= m; j++) {
      char x = getchar();
      while (x != '.' && x != '*') {
        x = getchar();
      }
      a[i][j] = x == '.';
    }
  }
  for (rint j = 1; j <= m; j++) {
    for (rint i = 1; i <= n; i++) {
      if (a[i][j]) h[i][j] = h[i - 1][j] + 1;
      else h[i][j] = 0;
    }
  }
  long long ans = 0ll;
  for (rint i = 1; i <= n; i++) {
    while (!deq.empty()) deq.pop_back();
    for (rint j = 1; j <= m; j++) {
      push_l(i, j);
    } 
    while (!deq.empty()) r[i][deq.back()] = m + 1, deq.pop_back();
    for (rint j = m; j >= 1; j--) {
      push_r(i, j);
    }
    while (!deq.empty()) l[i][deq.back()] = 0, deq.pop_back();
    for (rint j = 1; j <= m; j++) {
      //printf("l[%d][%d] = %d, r[%d][%d] = %d\n", i, j, l[i][j], i, j, r[i][j]);
      //printf("h[%d][%d] = %d\n", i, j, h[i][j]);
      ans += 1ll * (j - l[i][j]) * (r[i][j] - j) * h[i][j];
    }
  }
  printf("%lld\n", ans);
  return 0;
}