链接：https://nanti.jisuanke.com/t/17410

分析：正向分析给跪了。。逆向考虑的话，先模拟一遍，记录下每个黑点被第一次涂黑的时间，然后按时间倒着来，每次把该时间变黑的那些块变白，然后ans++，然后考虑加了这一块以后连通了某些块（包括刚刚变白的这块），把通过连通减少的减去，更新答案即可。最后一个的答案可以用dfs搞一下，注意直接递归写会爆栈。。

复杂度为O（n*m*q）。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 using namespace std; 8 const int maxn=1001,inf=1e9; 9 int p[maxn*maxn]; 10 int Find(int x){ return p[x]==x?x:p[x]=Find(p[x]);} 11 int n,m,q,color[maxn][maxn]; 12 int ans[10005]; 13 bool vis[maxn][maxn]; 14 vector
           
             t[10005]; 15 void Print(){ 16 for(int i=1;i<=n;i++){ 17 for(int j=1;j<=m;j++){ 18 int x=Find(i*maxn+j); 19 cout<
            
              sta; 30 sta.push(Statu(x,y)); 31 while(!sta.empty()){ 32 x=sta.top().x;y=sta.top().y; 33 p[x*maxn+y]=fa; 34 sta.pop(); 35 if(x
             
              1&&!color[x-1][y]&&!vis[x-1][y]){ 39 vis[x-1][y]=true;sta.push(Statu(x-1,y)); 40 } 41 if(y
              
               1&&!color[x][y-1]&&!vis[x][y-1]){ 45 vis[x][y-1]=true;sta.push(Statu(x,y-1)); 46 } 47 } 48 } 49 int main(){ 50 scanf("%d%d%d",&n,&m,&q); 51 int x1,y1,x2,y2; 52 for(int i=1;i<=n;i++){ 53 for(int j=1;j<=m;j++) 54 p[i*maxn+j]=i*maxn+j; 55 } 56 for(int i=0;i
               
                0;T--){ 82 ans[T]=ans[T+1]; 83 for(int i=0;i
                
                 1&&!color[x-1][y]){ 89 H=Find((x-1)*maxn+y); 90 if(H!=Fa){ 91 ans[T]--; 92 p[H]=Fa; 93 } 94 count++; 95 } 96 if(x
                 
                  1&&!color[x][y-1]){105 H=Find(x*maxn+y-1);106 if(H!=Fa){107 ans[T]--;108 p[H]=Fa;109 }110 count++;111 }112 if(y