2782矩形计数题解

题意

一个 $n \times m$ 的平面直角坐标系，并给定 $k$ 个点，求至少包含一个点的矩形数量 $n \le 10^9$，$m \le 10^9$，$k \le 1000$

思路

首先，不难注意到时间复杂度是 $k$ 的平方级左右(比如$O(k^2\times log{k})$或$O(k^2)$)

考虑二维问题，常见定一维，处理一维，所以就枚举一个 $k^2$ 的上下边界，然后发现另一维度可以由二维dp解决

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template<class T, class U>
inline bool chmax(T& a, const U& b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template<class T, class U>
inline bool chmin(T& a, const U& b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
constexpr size_t N = 1005;
constexpr int MOD = 1000000007;
using point = array<int, 2>;
int n, m, k;
point a[N];
int sorted[N], s;
ll dp[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("rectangle.in", "r", stdin);
    freopen("rectangle.out", "w", stdout);
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++)
    {
        cin >> a[i][0] >> a[i][1];
        sorted[i] = a[i][0];
    }
    sort(a + 1, a + k + 1);
    set<int> st;
    for (int i = 1; i <= k; i++)
    {
        st.clear();
        dp[i][i] = a[i][1] * ll(m - a[i][1] + 1) % MOD;
        st.insert(a[i][1]);
        for (int j = i + 1; j <= k; j++)
        {
            int y = a[j][1];
            auto it = st.lower_bound(a[j][1]);
            if (it != st.end() && *it == y)
            {
                dp[i][j] = dp[i][j - 1];
                continue;
            }
            int pre = (it == st.begin() ? 0 : *prev(it));
            if (it != st.end() && *it == a[j][1])
            {
                it++;
            }
            int nxt = (it == st.end() ? m + 1 : *it);
            dp[i][j] = (dp[i][j - 1] + (nxt - y) * ll(y - pre)) % MOD;
            st.insert(a[j][1]);
        }
    }
    sort(sorted + 1, sorted + k + 1);
    s = unique(sorted + 1, sorted + k + 1) - sorted - 1;
    sorted[s + 1] = n + 1;
    int res = 0;
    for (int i = 1; i <= s; i++)
    {
        int x1 = lower_bound(a + 1, a + k + 1, point{sorted[i], 0}) - a;
        ll dx1 = sorted[i] - sorted[i - 1];
        for (int j = i; j <= s; j++)
        {
            int x2 = lower_bound(a + x1, a + k + 1, point{sorted[j + 1], 0}) - a - 1;
            ll p = dx1 * (sorted[j + 1] - sorted[j]) % MOD;
            res = (res + p * dp[x1][x2]) % MOD;
        }
    }
    cout << res << '\n';
    return 0;
}

有问题请直接在评论区@我