专栏文章

题解：P13647 [NOISG 2016] Fabric

PP2441MPM2.4
P13647题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mimzl7tk
此快照首次捕获于
2025/12/01 18:08
3 个月前
此快照最后确认于
2025/12/01 18:08
3 个月前
查看原文

题意

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

题解

简单题，击杀了。
考虑枚举矩形下边界 dd，设 hih_i 为从 (i,d)(i,d) 向上的极长 00 段的长度。将 h1∼mh_{1\sim m} 视作一个直方图，考虑在这上面分析问题。
思考 k=1k=1 怎么做。直方图问题可以想到 P6453 的 trick，对 hh 建出小根笛卡尔树，笛卡尔树上的每个节点都对应了直方图上的一个块。对每个节点 uu 计算贡献，设其对应在序列上的下标区间为 [lu,ru][l_u,r_u]，则相当于要求矩形的左右边界 [l,r]⊆[lu,ru][l,r]\subseteq [l_u,r_u]，上边界 y∈[hfau+1,hu]y\in [h_{fa_u}+1,h_u]，因此贡献就是 (hu−hfau)×szu(szu+1)2(h_u-h_{fa_u})\times \dfrac{sz_u(sz_u+1)}{2}，其中 szu=ru−lu+1sz_u=r_u-l_u+1 为 uu 的子树大小。时间复杂度为 O(nm)\mathcal{O}(nm)。
思考正解怎么做。不妨暴力枚举上边界 yy，那么对矩形长度 lenlen 有限制 ⌈yk⌉≤len≤szu\left\lceil\dfrac{y}{k}\right\rceil\leq len\leq sz_u，于是贡献为
∑y=hfau+1hu∑len=⌈y/k⌉szu(szu−len+1)=∑y=hfau+1hu∑i=1szu−⌈y/k⌉+1i=∑y=hfau+1hu[szu−⌈yk⌉+1≥0](szu−⌈yk⌉+1)(szu−⌈yk⌉+2)2\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)=∑y=1h[w−⌈yk⌉+1≥0](w−⌈yk⌉+1)(w−⌈yk⌉+2)2f(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}
可以直接 O(nm)\mathcal{O}(nm) 递推：
f(w,h)=f(w,h−1)+[w−⌈hk⌉+1≥0](w−⌈hk⌉+1)(w−⌈hk⌉+2)2f(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}
这样节点 uu 的贡献就是 f(szu,hu)−f(szu,hfau)f(sz_u,h_u)-f(sz_u,h_{fa_u}) 了。直接累加即可，时间复杂度还是 O(nm)\mathcal{O}(nm)。
代码CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...