题解： AT_abc391_d [ABC391D] Gravity

FlowerAccepted · 2025-02-02 16:02:36 · 题解

解题思路

注意到落下的正方形们满一行才会被消除，之后的正方形才会落下来。所以能清除多少行正方形和正方形们初始的高度无关，而是等于同一个 X 中最少有多少个正方形。如图 \text{S-AT\_abc391\_d-1} 所示，没有正方形会被消除：

在加入一个绿色正方形后，最底部的一行才会被消除，如图 \text{S-AT\_abc391\_d-2} 所示：

我们可以使用一个 vector<int> v[MAXM] 来存储每一列从低到高的正方形。

具体的，可以按顺序输入到两个 pair<int, int> 数组 a[MAXN] 和 b[MAXN]，将 X_i 输入到 a_i.first（）；将 Y_i 输入到 a_i.second，再将 a 拷贝一份到 b，以便后用。（当然输入到 b，拷贝到 a 也是一样的。）

再将 a 按 second 不降序排序，这需要自定义比较函数

bool cmp(pair<int, int> x, pair<int, int> y) {
    return x.second < y.second;
}

再使用 sort(a + 1, a + n + 1, cmp) 进行排序。当然，你要愿意手搓 \tt STL 我也不会拦你。

然后按顺序遍历 a 数组，\forall 1 \le i \le N，在 v_{a_i.first} 的尾部追加 a_i.second，这样保证了表示每一列的向量中，下标越大的正方形越高，即正方形的高度呈升序排列，代码如下：

for (int i = 1; i <= n; i ++) {
    v[a[i].first].push_back(a[i].second);
}

图 \text{S-AT\_abc391\_d-1} 处理前后如图 \text{S-AT\_abc391\_d-3} 所示：

记 mins 为每个 v_i 中最少有多少个正方形；maxs 为每个 v_i 中最多有多少个正方形。

图 \text{S-AT\_abc391\_d-1} 中，mins = 0，maxs = 2；图 \text{S-AT\_abc391\_d-3} 中，mins = 1，maxs = 2;

我们开一个大小为 maxs 的向量 t，记录每一层正方形的消失时间，

这里 \inf 取 1e9+5 即可。

看不懂？上代码！

t.resize(maxs + 5); // 开大一点
for (int j = 1; j <= w; j ++) {
    for (int i = 0; i < mins; i ++) {
        t[i] = max(t[i], v[j][i]);
    }
}
for (int i = mins; i < maxs; i ++) {
    t[i] = 1e9 + 5;
}

还看不懂？上图片！

预处理完毕，开是处理询问。

对于每个询问，首先注意输入顺序。（编者被坑了！）

接着找到对应的正方形对应的层数 id，一定要使用原来顺序的 b 数组查找。这可以使用 lower_bound 来优化，返回的是指针，注意减去开头：

id = (int)(lower_bound(v[b[A].first].begin(), v[b[A].first].end(), b[A].second) - v[b[A].first].begin());

然后注意到正方形若在 T_i 时刻没有正在消失，那么它在 T_i + 0.5 时刻就还存在。

最后，根据预处理的结论，判断 T_i 是否小于 t_{id} 即可。如果 id \ge mins，说明这层没凑齐，正方形自然就不会下落了，T_i 不会超过 \inf（10^9+5）。

这块内容如果不理解还请看看图 \text{S-AT\_abc391\_d-4}。

代码呈现

代码不丑，请参考。

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector> // 万能头不是 STL 成员，咱不用。
using namespace std;

pair<int, int> a[200005], b[200005];
vector<int> v[200005], t; // 防止越界，开大数组，从我做起

bool cmp(pair<int, int> x, pair<int, int> y) { // 比较数对
    return x.second < y.second;
}

int main() {
    int n, w, mins = 1e9+5, maxs = 0, q, A, T, id;
    cin >> n >> w;
    for (int i = 1; i <= n; i ++) {
        cin >> b[i].first >> b[i].second;
        a[i] = b[i];
    } // 输入
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i ++) {
        v[a[i].first].push_back(a[i].second);
    } // 离散化？？
    for (int i = 1; i <= w; i ++) {
        mins = min(mins, (int)v[i].size());
        maxs = max(maxs, (int)v[i].size());
    } // 计算层数
    t.resize(maxs + 5);
    for (int j = 1; j <= w; j ++) {
        for (int i = 0; i < mins; i ++) {
            t[i] = max(t[i], v[j][i]);
        }
    } // 计算每一层的消失时间
    for (int i = mins; i < maxs; i ++) {
        t[i] = 1e9 + 5;
    } // inf
    cin >> q;
    for (int i = 1; i <= q; i ++) {
        cin >> T >> A;
        id = (int)(lower_bound(v[b[A].first].begin(), v[b[A].first].end(), b[A].second) - v[b[A].first].begin()); // 二分
        cout << (T < t[id] ? "Yes\n" : "No\n"); // 换行！
    }
    return 0;
}

至此，本题 Accepted。

复杂度分析

预处理除排序外的均摊复杂度是 O(N)，这是因为无论单层还是双层的循环，总的循环次数也不会也不会超过 N 次。