题解：P12561 [UTS 2024] Matrix

xubaichuan · 2026-09-06 15:40:57 · 题解

题解都在干什么，这题难道不是裸的三维数点吗？

考虑什么时候 (i_1, j_1) 可以对以 (i_2, j_2) 为起点的三角形做贡献，发现当且仅当满足下面三个条件：

其中，第三个条件等价于：j_1 - i_1 \le j_2 - i_2 + k - 1，然后就是三维数点 CDQ 分治板子了。

因为这题前两维限制都在矩阵上，所以不需要显式实现 CDQ。算上树状数组，总时间复杂度 O(nm \log \min(n, m) \log (n+m))。我比较懒，写的是 O(nm \log m \log (n+m)) 的。

不管是时间还是空间，这个做法的常数都很小，不怎么卡常。注意一下常数，就能拿下最优解 rk1。

参考代码（非最优解版本）：

#include <bits/stdc++.h>

using namespace std;

using info = array<int, 2>;

info operator + (const info& a, const info& b) {
    if (a[0] > b[0]) {
        return a;
    } else if (a[0] < b[0]) {
        return b;
    } else {
        return {a[0], a[1] + b[1]};
    }
}

template<int N>
struct Fenwick {
    info tr[N];

    void clear() {
        fill(tr, tr + N, info{-1, 0});
    }
    void add(int i, info v) {
        for (; i < N; i += i & -i) {
            tr[i] = tr[i] + v;
        } 
    }
    info query(int i) {
        i = min(i, N - 1);
        info res{-1, 0};
        for (; i > 0; i -= i & -i) {
            res = res + tr[i];
        }
        return res;
    }
};

const int N = 2005;

int n, m, k, a[N][N];
info ans[N][N];

Fenwick<N * 2> fw;

void solve(int l, int r) {
    if (l == r) {
        fw.clear();
        for (int i = 1; i <= n; i++) {
            fw.add(l - i + n, {a[i][l], 1});
            ans[i][l] = ans[i][l] + fw.query(l - i + n + k - 1);
        }
        return ;
    }
    int mid = l + r >> 1;
    solve(l, mid);
    solve(mid + 1, r);
    fw.clear();
    for (int i = 1; i <= n; i++) {
        for (int j = mid + 1; j <= r; j++) {
            fw.add(j - i + n, {a[i][j], 1});
        }
        for (int j = l; j <= mid; j++) {
            ans[i][j] = ans[i][j] + fw.query(j - i + n + k - 1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            ans[i][j] = {-1, 0};
        }
    }

    solve(1, m);

    for (int i = k; i <= n; i++) {
        for (int j = 1; j + k - 1 <= m; j++) {
            cout << ans[i][j][0] << ' ';
        }
        cout << '\n';
    }
    for (int i = k; i <= n; i++) {
        for (int j = 1; j + k - 1 <= m; j++) {
            cout << ans[i][j][1] << ' ';
        }
        cout << '\n';
    }
    return 0;
}