2022 年牛客多校第九场 F 题题解

F Matrix and GCD

题意：给定 $n\times mn\; \backslash times\; m$ 的矩阵，其中 $[1,nm][1,nm]$ 的数字均只出现一次，问所有的连续子矩阵的 $\gcd \backslash gcd$ 之和。$n,m\le 1\times 10^{3}n,m\; \backslash leq\; 1\backslash times\; 10^3$。

解法：考虑 $\mathcal{O}(n\log n)\backslash mathcal\; O(n\; \backslash log\; n)$ 的倍数枚举，统计有 $f_{i}f\_i$ 个连续子矩形其中全部的数字均是 $ii$ 的倍数，再进行容斥，答案为 ${\displaystyle \sum _{i=1}^{nm}\mu (i)f_i}\backslash displaystyle\; \backslash sum\_\{i=1\}^\{nm\}\; \backslash mu(i)f\_i$。

因而问题转化为，$n\times mn\backslash times\; m$ 的矩形中，有 $kk$ 个特殊格点，问有几个矩形是完全由特殊格点组成的。首先先 $\mathcal{O}(k\log k)\backslash mathcal\; O(k\; \backslash log\; k)$ 的进行排序，然后 $\mathcal{O}(k)\backslash mathcal\; O(k)$ 的从下往上统计每个点垂直往下有多少个连续的特殊格点，然后横向枚举每个格点，用单调栈在线性时间内计算出以当前格点为左上角有多少个矩形，一次计算一整个横向连续段。因而对于一个连通块只需要 $\mathcal{O}(k)\backslash mathcal\; O(k)$ 的时间，因而总的时间复杂度为 $\mathcal{O}(nm{}^{2}nm)\backslash mathcal\; O(nm\; \backslash log^2\; nm)$。

#include <bits/stdc++.h>
#define fp(i, a, b) for (int i = a, i##_ = (b) + 1; i < i##_; ++i)
#define fd(i, a, b) for (int i = a, i##_ = (b) - 1; i > i##_; --i)

using namespace std;
const int N = 1e3 + 5, M = 1e6 + 5;
using ll = int64_t;
int n, m, a[N][N], vis[N][N], H[N][N];
pair<int, int> pos[M];
ll calc(int *h, int k) {//计算矩形个数
    stack<int> s;
    vector<int> l(k), r(k);
    fd(i, k - 1, 0) {
        while (!s.empty() && h[i] <= h[s.top()]) l[s.top()] = i, s.pop();
        s.push(i);
    }
    while (!s.empty()) l[s.top()] = -1, s.pop();
    fp(i, 0, k - 1) {
        while (!s.empty() && h[i] < h[s.top()]) r[s.top()] = i, s.pop();
        s.push(i);
    }
    while (!s.empty()) r[s.top()] = k, s.pop();
    ll res = 0;
    fp(i, 0, k - 1) res += (ll)h[i] * (i - l[i]) * (r[i] - i);
    return res;
}
void Solve() {
    scanf("%d%d", &n, &m);
    fp(i, 1, n) fp(j, 1, m)
        scanf("%d", a[i] + j), pos[a[i][j]] = {i, j};
    int k = n * m;
    vector<ll> cnt(k + 1);
    fp(d, 1, k) {
        vector<pair<int, int>> a;
        for (int t = d; t <= k; t += d) {
            auto [x, y] = pos[t];
            vis[x][y] = 1, a.push_back({x, y});
        }
        sort(a.begin(), a.end());
        for (int i = a.size() - 1; ~i; --i) {
            auto [x, y] = a[i];
            H[x][y] = vis[x + 1][y] ? H[x + 1][y] + 1 : 1;
        }
        for (int i = 0, j; i < a.size(); i = j + 1) {
            for (j = i; j + 1 < a.size() && a[j + 1].first == a[i].first && a[j + 1].second == a[j].second + 1; ++j);
            cnt[d] += calc(H[a[i].first] + a[i].second, j - i + 1);
        }
        for (auto [x, y] : a) vis[x][y] = 0;
    }
    ll ans = 0;
    fd(d, k, 1) {
        for (int t = 2 * d; t <= k; t += d)
            cnt[d] -= cnt[t];
        ans += cnt[d] * d;
    }
    printf("%lld\n", ans);
}
int main() {
    int t = 1;
    while (t--) Solve();
    return 0;
}