本文共 3259 字，大约阅读时间需要 10 分钟。

题解

About F1

首先我们应该很容易想到建图。

对于一个沙子，向它左，右，上，下四个方向能影响到的最近的沙子连边，很明显，通过这些方块总存在一条到其它能影响到的沙子。 我们要找的，就是选择尽量少的沙子使得它将所有点都覆盖到。 但这连出来的图是存在环的，环内的沙子是会互相影响的。 这是我们就需要缩点了，缩点后得到的无环有向图，选择所有入度为零的沙子即可。 时间复杂度$O\left(nm\right)$。

About F2

对于这个图，我们只需要让第$i$列的第$a_i$块掉下来即可，它们掉了，下面的自然也会掉。

我们还是先建图，跑tarjan缩点。 但对于包含第$i$列第$a_i$个的，我们称其为关键点。我们的目的就是让所有的关键点都掉下去。 对于可以被其它关键点走到的关键点，是没有意义的，我们可以不管它们。

之后我们可以发现，对于任何一个点，它能够走到的关键点的区间是连续的。

如果存在$i<j<k$使得$i$列与$k$列的对应的关键点能被走到，但$j$列不能。那么$i$列与$k$列一定可以通过$j$列中的一个点联通。 如果这个点在$j$列的关键点之下，那么$j$列的关键点必然可以影响到$i$列与$k$列中的一个关键点。 如果这个点在$j$列的关键点之上，那么$j$列的关键点必然可以被$i$列或$k$列中的一个关键点影响到。 无论怎么都不满足我们的条件，所以其对应的区间必定是连续的。

所以我们可以先通过拓扑求出每个点对应的区间，然后将所有的区间按左端点排序，贪心选出最少的区间使其覆盖所有关键点即可。

时间复杂度$O\left(nmlognm\right)$。

源码

#include
   
    using namespace std;#define MAXN 400005#define lowbit(x) (x&-x)#define reg register#define mkpr make_pairtypedef long long LL;typedef unsigned long long uLL;const int INF=0x3f3f3f3f;const int mo=1e9+7;const int iv2=5e8+4;const int lim=1000000;const int jzm=2333;const int orG=3,invG=332748118;const double Pi=acos(-1.0);typedef pair
    
      pii;const double PI=acos(-1.0);template
     
      _T Fabs(_T x){
   return x<0?-x:x;}template
      
       void read(_T &x){
   	_T f=1;x=0;char s=getchar();	while(s>'9'||s<'0'){
   if(s=='-')f=-1;s=getchar();}	while('0'<=s&&s<='9'){
   x=(x<<3)+(x<<1)+(s^48);s=getchar();}	x*=f;}template
       
        void print(_T x){
   if(x<0){
   x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}int gcd(int a,int b){
   return !b?a:gcd(b,a%b);}int add(int x,int y){
   return x+y