J题题解：扫描线+双指针+并查集

答案等于，Bsize表示连通块尺寸，这个并不是难点，难点在于连通块大小怎么求。

这个题，第一眼：水题啊，直接并查集或者dfs瞎搞搞。
然后惨遭数据范围毒打。（毒瘤）
那...首先dfs先pass，这个怎么剪枝好像也不行，离散化压缩再dfs感觉也写不太动。
但是并查集是个好思路。
首先根据数据范围，只要地图足够大，障碍物的总数目有有限，障碍物就放的相当稀疏，那我可以提前把一些比较大的连通块并起来。

idea1

如图，'.'表示普通的格子，'X'表示障碍物。
我可以按照行进行扫描，然后把所有连在一起的.合并成一个长长的“面条”，这样子再把行间相邻的“面条”给合并起来不就好了？

（...一段时间后...）

再次被毒打（毒瘤啊）
为啥呢，因为竟然有这样的数据。


题目仅保证了，而我的算法是的。
只要T=,nm拉满，每次放一个我就凉了。

idea2

在刚才算法的基础上，我们进行优化。
既然明明知道它障碍物放的很稀疏嘛，那如果连续多个行之间都没有放任何障碍物，也太浪费了。
只要碰到这种情况，我们就给他压缩成一行（也就是离散化一下）。
这里还是提供一组样例

.....X.....
.....X.....
....XXX....
...X...X...
....XXX....
XXXX.......
...........
....X......
...........
...........
.......X...
...........

12 11
16
1 6
2 6
3 5
3 6
3 7
4 4
4 8
5 5
5 6
5 7
6 1
6 2
6 3
6 4
8 5
11 8

用“面条”分解后如图所示。
然后就是“面条”怎么合并的问题。
实际上这是个经典问题，问题转化成
给你两个数组，数组里面存了一些线段，线段在组内是无交的，问你来自第一个组的线段与来自第二个组之间的线段有哪些是相交的。
这是个经典的two pointer双指针问题。
首先对两个数组中的线段进行排序。
它有单调性，所以可以做双指针。
假设来自第一个数组中的第i条线段最远可以交到来自第二个数组中的第j条线段，那么来自第一个数组中的第i+1条线段至少可以交得到第二个数组中的第j条线段。
假设来自第一个数组中的第i条线段最近交不到来自第二个数组中的第j条线段，那么来自第一个数组中的第i+1条线段一定交不到第二个数组中的第j条线段。
（听不懂没关系，听不懂你可以二分，就多个log，这并不重要）
如果直接穷举所有的相交关系来并的话，它还是的。
然后因为是并查集嘛，你不用和所有人都并起来，每次都只选集合中的一个人并就好了。
那最简单的并法就是每次都选那个最远交到的线段并。

所以双指针扫描，每次都只选择指针位置靠前的指针往后面移动（这样就能保证每条线段并的人都是另一组中它能够并得到的最远的那个，我们让它来当并查集的代表元就好）

for(int i=2;i<totrow;++i)
{
    int pin1=0,pin2=0;
    while(pin1<lists[i-1].size()&&pin2<lists[i].size())
    {
        if(has_cross(lists[i-1][pin1].l,lists[i-1][pin1].r,lists[i][pin2].l,lists[i][pin2].r))
        {
            unions(lists[i-1][pin1].id,lists[i][pin2].id);
        }
        if(lists[i-1][pin1].r<=lists[i][pin2].r)
        {
            ++pin1;
        }
        else
        {
            ++pin2;
        }
    }
}

那这个题就做完了。
前面“切面条”的过程就是个模拟题。
首先按照行作为第一关键字，列作为第二关键字进行排序。
然后这个“面条”分为3类。
1、第一个障碍物之前的面条（可能没有，最多2个）
2、最后一个障碍物之后的面条（可能没有，最多2个）
3、两个相邻（排序后在数组中相邻）障碍物之间的面条（可能没有，最多3个）
，对于1,2，这个真就随便写啊。
对于3，其实也并不复杂。

如图所示，我们for过去，每次只处理第i个障碍物与第i-1个障碍物后面出现的“面条”
然后分成
①在同一行
②在不同行并且物理上不相邻
③在同一行并且物理上是相邻的