题解：P13647 [NOISG 2016] Fabric

· · 题解

模拟赛 T4。笔者在赛时得到了一个 O(nm \log nm) 的做法，但没调出来遗憾离场。之后看到了 ABC420F 的题解，发现直接暴力重构是对的，因此写一篇题解。

先考虑 k=1 怎么做。这是 P1950，做法是处理出每个点向上的连续段长度 h_{i,j}，然后枚举并钦定矩形的右下角 (x,y)，计算方案数。

如图，对于一个右下角在 (x,y) 的矩形，可以发现其左边界为满足 z<y 且 h_{x,z}>h_{x,y} 的最大的 z。那么这个矩形的方案数就是 (z-y+1)h_{x,y}。不难发现这不会算重也不会算漏。下文视 n, m 同阶，单调栈求出 z 可以做到 O(n^2)。

然后带上面积限制。可以发现当前高度 i 下面积至少为 k 的最小宽度为 w=\lceil \dfrac{k}{i} \rceil，则对于一个长为 j 的连续段，宽度在 [w,j] 之间的矩形都满足条件，贡献为 \dfrac{1}{2}(j-w+1)(j-w+2)。直接顺序扫描可以做到 O(n^3)。

笔者的赛时想法是用一堆线段树来维护这些连续段，或者离线以后整一堆树状数组，没调出来失败了。

有这样一个想法：对于同一行 x，从大到小加入每个 h_{x,y}。可以用一个类似链表的东西维护连续段。这也可以看作是一条从上到下的扫描线，我们只对扫描线以上的柱子所形成的连续段计算答案。

然而我们发现 w 变化时连续段的贡献也变了。比如说下面这张图，扫描线下降时橙色框标出的连续段的高度也下降了，对于一些 k 其贡献必然改变。

接下来是很巧妙的一步：注意到 w=\lceil \dfrac{k}{i} \rceil，根据数论分块的结论，它只有 O(\sqrt{k}) 种取值，所以直接暴力重构，复杂度为 O(n \sqrt{k})=O(n\sqrt{nm})=O(n^2)，是正确的！不需要单调栈笛卡尔树等数据结构。

:::info[代码]

const int N = 2005;

int n, m, k, a[N][N], h[N][N];
bool vis[N][N];
int64 f[N], cnt[N];
vector<pair<int, int>> vec[N];

struct node {
    int l[N], r[N];
    int64 merge(int x) {
        int64 res = 0;
        int a = x - l[x - 1], b = r[x + 1] - x, c;
        cnt[a]--, cnt[b]--, res -= f[a] + f[b];
        r[l[x - 1]] = r[x + 1], l[r[x + 1]] = l[x - 1];
        return c = r[x + 1] - l[x - 1] + 1, cnt[c]++, res += f[c];
    }
    int64 mergel(int x) {
        int64 res = 0;
        int a = x - l[x - 1], c;
        cnt[a]--, res -= f[a];
        r[l[x - 1]] = x, l[x] = l[x - 1];
        return c = x - l[x - 1] + 1, cnt[c]++, res += f[c];
    }
    int64 merger(int x) {
        int64 res = 0;
        int b = r[x + 1] - x, c;
        cnt[b]--, res -= f[b];
        l[r[x + 1]] = x, r[x] = r[x + 1];
        return c = r[x + 1] - x + 1, cnt[c]++, res += f[c];
    }
    int64 create(int x) {return cnt[1]++, l[x] = r[x] = x, f[1];}
} l[N];

void _main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == 0) h[i][j] = h[i - 1][j] + 1, vec[h[i][j]].emplace_back(i, j);
        }
    }
    int64 res = 0, cur = 0;
    for (int i = n; i >= 1; i--) {
        int w = (k + i - 1) / i;
        auto rebuild = [&]() -> void {
            fill(f + 1, f + w, 0), cur = 0;
            for (int j = w; j <= m; j++) {
                f[j] = 1LL * (j - w + 1) * (j - w + 2) / 2;
                cur += 1LL * cnt[j] * f[j];
            }
        };
        if (i == n || w != (k + i) / (i + 1)) rebuild();

        for (const auto& pos : vec[i]) {
            int x = pos.first, y = pos.second;
            if (vis[x][y - 1] && vis[x][y + 1]) cur += l[x].merge(y);
            else if (vis[x][y - 1]) cur += l[x].mergel(y);
            else if (vis[x][y + 1]) cur += l[x].merger(y);
            else cur += l[x].create(y);
            vis[x][y] = true;
        }
        res += cur;
    } cout << res;
}

:::