解题报告

问题简述

    一个的矩形，每次将矩形中的某一个小矩形区域用刀切下来。进行若干次这样的操作，请问每次操作切下来的矩形部分是多少个小连通块。比如：

在这个图中，假设灰色部分在做这次切割之前就已经被割下，那么切出红色矩形，切下来的矩形部分分成了如图所示的四个小连通部分。

算法分析

每次切除操作事实上可以看作两步，第一步是求出要切除的部分中连通块的个数，第二步是将所有该切除的方格都从大矩形中去除。直接做的时间复杂度肯定是无法承受的，每次操作最坏可能达到O(nm)。

也许我们会想到使用某些特殊的数据结构辅助，但是这样的效果也不好，毕竟很少有数据结构能够处理题目中所给出的特殊的询问方式——某一子矩形中的连通块个数。

其实这道题目有一个最大的特点，也是本题解题的关键：这里只有切除操作！也就是说，所有的单位格都只会被切除一次！试想我们设计一个这样的算法，每次切除矩形的时候，利用某种方法，快速的找出要切除的矩形中残余的小方格，并进行BFS遍历，找到相关的连通分量，在BFS遍历的同时将它们从矩形中删除。这样由于所有的单元格都只被删除一次，按照这个思路在最理想的情况下所有操作的总时间复杂度是O(nm+p)的。

但是这可能么？我们还有一个问题没有解决，怎么样快速的找到矩阵中残余的小方块呢？如果将整个矩阵扫描一遍，那么我们等于又回到了原地，时间复杂度最坏还是O(nm)的。这里介绍一种使用并查集的方法，对于每一行我们分别建立一个并查集，如果同一行相邻的两个格子同时都已经被切除了的话，那么就认为这两个格子是同一个集合的，我们每次扫描事实上就是找某一个集合的最右边的一个元素是什么：

而删除一个方格，事实上就是将两个集合合并而已：

这样当进行一次切割的时候，我们每一行都用并查集这样的扫描，快速锁定每一行的残余元素就可以了。

我们来分析一下时间复杂度，首先每个方格只可能被删除一次，而每次从并查集中删除就相当于合并操作，时间复杂度为，所以删除部分总时间复杂度为，而每次操作需要对每一行都进行一次扫描，也就是查找操作，这个总时间复杂度为，所以总时间复杂度是，按照题目的数据范围是可以出解的。