题解：P13647 [NOISG 2016] Fabric

· · 题解

题意

给定一个 n\times m 的 0/1 网格，求有多少个面积至少为 k 的全 0 矩形。1\leq n,m\leq 2\times 10^3，1\leq k\leq nm。

题解

简单题，击杀了。

考虑枚举矩形下边界 d，设 h_i 为从 (i,d) 向上的极长 0 段的长度。将 h_{1\sim m} 视作一个直方图，考虑在这上面分析问题。

思考 k=1 怎么做。直方图问题可以想到 P6453 的 trick，对 h 建出小根笛卡尔树，笛卡尔树上的每个节点都对应了直方图上的一个块。对每个节点 u 计算贡献，设其对应在序列上的下标区间为 [l_u,r_u]，则相当于要求矩形的左右边界 [l,r]\subseteq [l_u,r_u]，上边界 y\in [h_{fa_u}+1,h_u]，因此贡献就是 (h_u-h_{fa_u})\times \dfrac{sz_u(sz_u+1)}{2}，其中 sz_u=r_u-l_u+1 为 u 的子树大小。时间复杂度为 \mathcal{O}(nm)。

思考正解怎么做。不妨暴力枚举上边界 y，那么对矩形长度 len 有限制 \left\lceil\dfrac{y}{k}\right\rceil\leq len\leq sz_u，于是贡献为

\begin{align*} &\sum_{y=h_{fa_u}+1}^{h_u}\sum_{len=\left\lceil y/k\right\rceil}^{sz_u}(sz_u-len+1)\\ =&\sum_{y=h_{fa_u}+1}^{h_u}\sum_{i=1}^{sz_u-\lceil y/k\rceil+1}i\\ =&\sum_{y=h_{fa_u}+1}^{h_u}\left[sz_u-\left\lceil \dfrac{y}{k}\right\rceil+1\geq 0\right]\frac{\left(sz_u-\left\lceil \dfrac{y}{k}\right\rceil+1\right)\left(sz_u-\left\lceil \dfrac{y}{k}\right\rceil+2\right)}{2} \end{align*}

考虑预处理出

f(w,h)=\sum\limits_{y=1}^h \left[w-\left\lceil \dfrac{y}{k}\right\rceil+1\geq 0\right]\frac{\left(w-\left\lceil \dfrac{y}{k}\right\rceil+1\right)\left(w-\left\lceil \dfrac{y}{k}\right\rceil+2\right)}{2}

可以直接 \mathcal{O}(nm) 递推：

f(w,h)=f(w,h-1)+\left[w-\left\lceil \dfrac{h}{k}\right\rceil+1\geq 0\right]\dfrac{\left(w-\left\lceil \dfrac{h}{k}\right\rceil+1\right)\left(w-\left\lceil \dfrac{h}{k}\right\rceil+2\right)}{2}

这样节点 u 的贡献就是 f(sz_u,h_u)-f(sz_u,h_{fa_u}) 了。直接累加即可，时间复杂度还是 \mathcal{O}(nm)。

:::success[代码]

#include <bits/stdc++.h>

using namespace std;

#define lowbit(x) ((x) & -(x))
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
const int N = 2e3 + 5;

template<typename T> inline void chk_min(T &x, T y) { x = min(x, y); }
template<typename T> inline void chk_max(T &x, T y) { x = max(x, y); }

int n, m, k, h[N], W[N];
int top, stk[N], ls[N], rs[N];
ll ans, suf[N], f[N][N];
bool a[N][N];

ll calc(ll x) { return x * (x + 1) >> 1; }
void prework() {
    for (int w = 1; w <= m; ++w) for (int h = 1; h <= n; ++h) {
        ll x = (k + h - 1) / h;
        f[w][h] = f[w][h - 1] + (x <= w ? calc(w - x + 1) : 0);
    }
}
int build() {
    top = 0, fill(ls + 1, ls + m + 1, 0), fill(rs + 1, rs + m + 1, 0);
    for (int i = 1; i <= m; ++i) {
        while (top && h[stk[top]] >= h[i]) ls[i] = stk[top--];
        rs[stk[top]] = i, stk[++top] = i;
    }
    return stk[1];
}
void dfs(int x, int fx) {
    W[x] = 1;
    if (ls[x]) dfs(ls[x], x), W[x] += W[ls[x]];
    if (rs[x]) dfs(rs[x], x), W[x] += W[rs[x]];
    ans += f[W[x]][h[x]] - f[W[x]][h[fx]];
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> k, prework();
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> a[i][j];
    for (int d = 1; d <= n; ++d) {
        for (int i = 1; i <= m; ++i) h[i] = !a[d][i] ? h[i] + 1 : 0;
        dfs(build(), 0);
    }
    cout << ans;
    return 0;
}

:::