Rectangles

$\mathcal{O}(n^2)$ 做法（嘲讽 Sam $\mathcal{O}(n^2\log n)$）。

HDU 2013。

给定 $n,m,k$ 以及 $k$ 个关键点 $(X_i,Y_i)$。求有多少个 $1\le x_1\le x_2\le n,1\le y_1\le y_2\le m$，满足矩形 $(x_1,y_1)(x_2,y_2)$ 内部至少有一个关键点。

$1\le n,m\le 10^9,1\le k\le 1000$。

首先我们有一个错误的做法：

对于每一个关键点 $(X_i,Y_i)$，计算所有包含这个点的矩形个数，即 $X_iY_i(n-X_i+1)(m-Y_i+1)$ 个矩形。

然后将所有关键点的答案累加。

错误的原因是，一个矩形可能包含多个点，会被重复计算很多次。

于是为了保证不算重，我们在计算关键点 $(X_i,Y_i)$ 时，不妨钦定关键点 $i$ 为包含其的矩形中编号最大的。这样每一个矩形就只会在其编号最大的点处被计算。

为了方便，我们将所有关键点按 $X_i$ 为第一关键字，$Y_i$ 为第二关键字排序并去重。

那么枚举 $i$，计算时我就需要计算所有不包含编号 $>i$ 的矩形个数。

接下来有一个错误但是具有启发性的做法：

由于所有不能被矩形包含的关键点都在 $i$ 的右边或者上面，于是我们得出结论：$(x_1,y_1)$ 可以在 $1\sim X_i$ 和 $1\sim Y_i$ 内随便取（注意这里有问题）。

于是被限制的就只有 $(x_2,y_2)$ 了。

然后我们又发现，一个编号 $j(j>i)$ 的关键点被包含。当且仅当 $x_2\ge X_j,y_2\ge Y_j$，这可以看成是一个矩形覆盖，所有被覆盖的点都不能被选择。

那么我们可以使用单调栈处理这些点的面积并，然后拿总面积减去即可。

然而上面的实际上有问题：对于那些编号 $j(j>i)$ 的且 $Y_j<Y_i$ 的点，这些点实际上会影响 $(x_1,y_1)$！（自己画图）。

具体的，不妨设 $x_2,y_2$ 已经确定，那么对于那些 $j>i$ 的 $j$ 且 $Y_j<Y_i$，那么如果满足 $Y_j\ge y_1$，那么这个矩形就会包含 $j$！于是，尽管 $x_1$ 没有限制，但是 $y_1$ 必须 $\ge\max\limits_{Y_j<Y_i\land j>i}\{Y_j\}$。

那么在上面处理 $x_2,y_2$ 的单调栈的过程中，我们需要同步维护一个指针 $p$ 维护所有 $Y_j<Y_i$ 的 $j$，以及 $p$ 以前的最大值 $M$。那么如果上面单调栈得到的 $(x_2,y_2)$ 的方案数为 $S$，那么总答案就会累加 $SX_i(Y_i-M)$。

这样你就得到了暴打 $\mathcal{O}(n^2\log n)$ 的 $\mathcal{O}(n^2)$ 做法。

题意：给定 $n,m$ 和平面上的 $k$ 个点，数有多少个矩形（左下 $(x_1,y_1)$、右上 $(x_2,y_2)$，要求 $1\le x_1\le x_2\le n$、$1\le y_1\le y_2\le m$）里至少含一个给定点，答案对 $10^9+7$ 取模。

最直白的做法是把所有矩形都枚举一遍。先按输入把点打到一张二维前缀和表上，这样判断「某个矩形里有没有点」就是 $O(1)$ 的；然后四重循环枚举 $x_1\le x_2$ 与 $y_1\le y_2$，有就累加。

代价是 $\Theta(n^2m^2)$，可以过测试点 $1,2$，20 分。

直接数「至少包含一个给定点的矩形」不好数，改成按 x 方向分列枚举。

把 $k$ 个点的 $x$ 坐标去重排序，得到若干列 $v_1<v_2<\dots<v_t$（再加两个哨兵 $v_0=0$、$v_{t+1}=n+1$）。矩形的左边界 $x_1$ 落在哪两条相邻列之间、右边界 $x_2$ 落在哪两条之间，一共只有 $O(t^2)$ 种「列区间」可以枚举。

固定一段列区间（矩形至少要横跨第 $i$ 到第 $j$ 列里的点）之后再看 y 方向：

• 左边界 $x_1$ 只能在 $(v_{i-1},v_i]$ 里取，共 $v_i-v_{i-1}$ 种；
• 右边界 $x_2$ 只能在 $[v_j,v_{j+1})$ 里取，共 $v_{j+1}-v_j$ 种；
• 中间这些列的点，按 $y$ 从小到大依次插入有序集合。插入一个点 $y$ 时设它在已插入集合里的前驱、后继分别是 $b,t$，那么以这个点为最低点、且 y 区间内至少含一个点的 $(y_1,y_2)$ 对数正好是 $(t-y)(y-b)$。

把所有点这样累加起来，每一对合法的 $(y_1,y_2)$ 都会被「它包含的最低那个点」统计恰好一次，不重不漏。于是这段列区间的贡献就是

$$(\text{y 方向的合法区间数})\times(v_i-v_{i-1})\times(v_{j+1}-v_j)$$

对所有列区间求和即可。

列数不超过 $k+1$，每段列区间的 y 方向扫描用有序集合做，总复杂度 $O(k^2\log k)$。

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

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