个人思路：
每个点向相邻沙子连边，向本列和相邻 \(2\) 列下方第一个沙子连边。
对于一个 DAG，所有入度为 \(0\) 的点会覆盖全部点。我们缩点即可通过 F1。
但是这样做是过不了 F2 的。
我们发现一个沙子下落，其下面的所有沙子都会下落，也就是说，第 \(i\) 列从下往上第 \(a_i\) 个沙子一定会直接或间接下落。
我们维护每行取最上方的沙子，它一定能覆盖一个连续的区间。因为每行只能让相邻两列下落，不可能不连续。
那么我们只需要求出每列最高点的覆盖区间，这个问题就转化为了区间覆盖问题。
先求区间。
我们对每个点计算相邻两列不比这个点高的最高点的位置，对其建边。这可以通过从低往高枚举每一行实现。
我们从每列最高点分别向两边搜索，不断延边走，到达一个点后不断往上走直到上方相邻的点没沙子。以左边为例，在第 \(i\) 列小于 \(a_i\) 时，停止搜索，此时区间左端点就是 \(i+1\)。
然后区间覆盖，比较简单。
我们维护下标 \(now\) 与 \(R\)，表示当前覆盖了 \([1,now]\)，已有线段中可以覆盖到 \(R\)。到一个节点时，用以该节点为左端点的线段更新 \(R\)，如果这个点没有被覆盖，\(now \leftarrow R\)，表示直接覆盖到 \(R\)。
正解：
标签：覆盖,Hard,相邻,Version,区间,沙子,Falling,now,下落 From： https://www.cnblogs.com/Mysterious-Cat/p/17124284.html