P5953 [POI2018]Różnorodność 题解

jiangly · 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;
}