自动搬运

查看原文

来自洛谷，原作者为

	jiangly 这个家伙很菜，什么也没有留下

搬运于2025-08-24 22:15:56，当前版本为作者最后更新于2020-02-25 14:37:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给定一个 $n\times m$ 的矩阵 ($1\le n,m\le 3000$)，求所有 $k\times k$ 的子矩阵的不同元素个数，输出最大值以及和。

题解

对每种元素分开算，要求的就是一些 $k\times k$ 的矩形的并，用平衡树维护连续段，差分计算贡献即可。

时间复杂度：$O(nm\log m)$。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
int n, m, k;
std::vector<std::vector<int>> a, d;
std::map<int, int> s;
std::vector<std::vector<int>> pos;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> m >> k;
    a.assign(n, std::vector<int>(m));
    int maxA = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
            maxA = std::max(maxA, a[i][j]);
            --a[i][j];
        }
    }
    pos.resize(maxA);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            pos[a[i][j]].push_back(i * m + j);
    d.assign(n - k + 2, std::vector<int>(m - k + 2));
    for (int v = 0; v < maxA; ++v) {
        s.clear();
        s[0] = 0;
        s[m - k + 1] = -1;
        for (int p : pos[v]) {
            int x = p / m + 1, y = p % m + 1;
            int u = std::max(0, x - k), l = std::max(0, y - k);
            x = std::min(x, n - k + 1);
            y = std::min(y, m - k + 1);
            s[y] = std::prev(s.upper_bound(y)) -> second;
            auto it = std::prev(s.upper_bound(l));
            int up = std::max(it -> second, u), rt = std::next(it) -> first;
            ++d[up][l];
            --d[up][rt];
            --d[x][l];
            ++d[x][rt];
            ++it;
            s[l] = x;
            while (it -> first != y) {
                up = std::max(it -> second, u);
                int lf = it -> first;
                it = s.erase(it);
                rt = it -> first;
                ++d[up][lf];
                --d[up][rt];
                --d[x][lf];
                ++d[x][rt];
            }
        }
    }
    for (int i = 0; i <= n - k + 1; ++i)
        for (int j = 1; j <= m - k + 1; ++j)
            d[i][j] += d[i][j - 1];
    for (int i = 1; i <= n - k + 1; ++i)
        for (int j = 0; j <= m - k + 1; ++j)
            d[i][j] += d[i - 1][j];
    int max = 0;
    long long sum = 0;
    for (int i = 0; i < n - k + 1; ++i) {
        for (int j = 0; j < m - k + 1; ++j) {
            max = std::max(max, d[i][j]);
            sum += d[i][j];
        }
    }
    std::cout << max << " " << sum << "\n";
    return 0;
}