题解：P7306 [COCI2018-2019#1] Strah

· · 题解

题目大意

给定一个棋盘，求其中所有全由 . 组成的矩形面积和。

题目分析

先想暴力，可以暴力枚举右下角 (x_1, y_1)，然后枚举左上角的横坐标坐标，然后可以知道左上角纵坐标的范围，因为范围一定连续，运用等差数列求面积即可，时间复杂度 \mathcal O(n^3)。

然后考虑优化掉左上角横坐标的枚举，我们发现对于一个右下角，可选左上角的范围一定是类似阶梯状的，即成单调。容易想到用单调栈优化，根据每个点上方最靠下的不可选点，可以得到梯状范围，然后考虑怎么算贡献。

我们先从简单情况考虑，若可选区域为矩形，则与每个左上角所形成矩形面积如图。

考虑不规则图形，则面积依旧为所列表格上数字和。

我们令这个行列数想成的表为贡献表，则每个梯状区域的贡献即为形状对应于表格上的值之和。我们考虑如何快速算出每个梯状区域的贡献和，这个时候再去枚举显然就退化成暴力了，于是可以想到可以由前继状态推得，如下图，我们可以看为前继状态增加了若干增量，这个方法明显可行，数学推式子即可。

但是这个算法既不好推也不好写，容易算漏。所以我们可以考虑拆贡献，对于每个左上角，我们在单调栈中弹出时即为这个点对后续右下角没贡献了于是我们可以计算这一堆左上角对于已经枚举到的右下角所形成的贡献。

我们拆成一行行看，对于其中一行，其在贡献表上对于每格贡献的系数是形似 1\sim x 的一个数列。

于是我们不妨对于每个梯状区域，我们拆成若干个矩形，对于每个矩形如上述方法对贡献表乘上系数。

我们令

a_{i,j} = i\times j

为贡献表，再计算

s_{i,j} = \sum\limits_{k=1}^{k\le j} a_{i,k}

为贡献表横向前缀和。则

g_{i,j} = \sum\limits_{k=1}^{k\le j} s_{i,k}

为对于每个左上角所在行乘上系数后的贡献和。令

f_{i,j} = \sum\limits_{k=1}^{k\le i} g_{k,j}

为对于贡献和的纵向前缀和则对于一个矩形 (x_1,y_1)(x_2,y_2)，其贡献总和为 w_{x_1,y_1} - w_{x_1,y_{2}-1}。

则可 \mathcal O(1) 计算贡献和。总时间复杂度为 \mathcal O(n\times m)。

code

PS：赛时怕数组太大 MLE，4 个数组实际只开了两个，滚动用的。

#include <iostream>
#include <cstdio>
#include <stack>
#define LL long long

using namespace std;

const int N = 2e3 + 5;
int n, m, f[N][N], i, j;
LL ans, a[N][N], t[N][N];
string s[N];
struct node{
    int val, lf;
}now, tmp;
stack <node> q;

int main()
{
    scanf("%d %d", &n, &m);
    for(i = 1;i <= n;i++)
    {
        cin >> s[i];
        s[i] = "*" + s[i];
        for(j = 1;j <= m;j++)
        {
            if(s[i][j] == '#')  f[i][j] = 0;
            else f[i][j] = f[i-1][j] + 1;
        }
    }
    for(i = 1;i <= n;i++)
        for(j = 1;j <= m;j++)
            a[i][j] = i * j;
    for(i = 1;i <= n;i++)
        for(j = 1;j <= m;j++)
            t[i][j] = t[i][j-1] + a[i][j];
    for(i = 1;i <= n;i++)
        for(j = 1;j <= m;j++)
            a[i][j] = a[i][j-1] + t[i][j];
    for(i = 1;i <= n;i++)
        for(j = 1;j <= m;j++)
            t[i][j] = t[i-1][j] + a[i][j];
    for(i = 1;i <= n;i++)
    {
        for(j = 1;j <= m;j++)
        {
            now.val = f[i][j], now.lf = j;
            while(!q.empty() && q.top().val >= now.val)
            {
                tmp = q.top();
                q.pop();
                now.lf = tmp.lf;
                ans += t[tmp.val][j-tmp.lf];
                ans -= t[max(q.empty()?0:q.top().val, now.val)][j-tmp.lf];
            }
            q.push(now);
        }
        while(!q.empty())
        {
            tmp = q.top();
            q.pop();
            ans += t[tmp.val][m+1-tmp.lf];
            ans -= t[q.empty()?0ll:q.top().val][m+1-tmp.lf];
        }
    }
    printf("%lld\n", ans);
    return 0;
}