【题解】AtCoder Beginner Contest ABC391 D Gravity

题目大意

原题面链接

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

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

思路

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

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

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

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

那么在每一次询问的时候只要看 $ti_{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; // 更新
}