【题解】AtCoder Beginner Contest ABC391 D Gravity

题目大意

• 原题面链接

在一个 $10^9\times W$ 的平面里有 $N$ 个方块。我们用 $(x,y)$ 表示第 $x$ 列从下往上数的 $y$ 个位置。第 $i$ 个方块的位置是 $(x_i,y_i)$。现在执行无数次操作，每一次操作如下：

• 如果整个平面的最下面一行的 $W$ 个位置上都有方块，那么把这一行的方块都消除掉。
• 从下往上遍历每一个未被消除的方块，如果它不在最下面一行且它下面是空格子，将它向下移动一格。注意：只移动一格！

思路

观察数据范围，需要预处理。我们不妨令 $t{i}_i$ 表示第 $i$ 个方块什么时候被消除。对于无法被消除的方块，其 $t{i}_i$ 为极大值。我们可以拿样例来寻找突破口，样例解释里面的那个图片如下：

观察一下，第二次操作执行完和第三次操作执行完的结果是一样的，所以继续执行下去，结果不会改变。也就是说，第三次操作及以后的操作都是“无效操作”，而其中可以消除的操作只有第二次，我们将其称为“有意义”。稍加观察可以发现，有意义的操作数量是每一列方块数量的最小值，很容易证明出来。

每一次有意义的操作之前我们可能需要一些（有的时候不需要）操作来让所有方块掉到地上，这种操作我们称之为“预备操作”。不难发现，预备操作的结束时间是每一列最下面的方块的纵坐标的最大值减一。所以有意义的操作的结束时间就是每一列最下面的方块的纵坐标的最大值（有点绕），可以用来更新 $t{i}_i$。

一个很重要的问题：怎么预处理每一列的那堆格子？开个 vector 数组，具体实现看代码。

那么在每一次询问的时候只要看 $t{i}_{A_j}$ 与 $T_j$ 的大小关系即可。

预处理部分代码

其实有点小细节能 hack，见文末彩蛋。

for (int i = 1; i <= n; i++)
{cin >> x[i] >> y[i]; // 读入v[x[i]].push_back(i); // 这一列的方块ti[i] = 1e9 + 7; // 极大值
}
int mn = 1e9 + 7; // 极大值
for (int i = 1; i <= w; i++)
{int cnt = v[i].size(); // 强转一下// int 类型不能直接和 unsigned int 类型取 minmn = min(mn, cnt);
}
for (int i = 0; i < mn; i++)
{int mx = 0; // 计算最大值for (int j = 1; j <= w; j++)mx = max(mx, y[v[j][i]]);for (int j = 1; j <= w; j++)ti[v[j][i]] = mx; // 更新
}

完整代码

我的提交记录

时间复杂度分析

预处理里面有个双重循环，为什么没有超时呢？$mn$ 最大为 $N$，复杂度理论上来说是 $O(N\cdot W)$ 的，但是考虑到实际构造原因，其均摊时间复杂度是不会超时的，所以可以通过本题。

彩蛋

大框架没问题，有个小细节出锅了。请问题目保证输入按 $y_i$ 升序排序了吗？没有！得自己排个序。注意一下，得用结构体排序，既可以让变量对应上，也可以存储初始下标。正确版本我还没写，应该没啥太大区别，遇到问题欢迎在评论里问我或私信沟通哦！要是有其他问题或者 hack 数据也可以联系我哦！