APIO2017 斑斓之地

1D6y a。

回忆平面图欧拉公式。

\(V\) 为点数，\(E\) 为边数，\(F\) 为面数，\(C\) 为连通块数。

以下称河流为黑块，土地为白块。将白块看成点，四联通的白块之间连边，不难发现矩阵查询即询问导出子图的连通块数。考虑平面图欧拉公式，那么只需要求出导出子图的点数、面数以及边数即可。

点数是好求的，只需要查询矩阵内有多少白块即可。

边数也是好求的，考虑白块上下连边或者左右连边两种情况，容斥一下，只需要考虑相邻两块中存在黑块的情况。把上下相邻两个块的贡献标在上面的块，把左右相邻的两个块的贡献标在左边的块，就不会算重了。

同样，面数也是好求的。\(4\) 个白块组成 \(2\times 2\) 的子矩形时才会多产生一个面。同样容斥，把 \(2\times 2\) 矩形中黑块的贡献放在左上角，还有一种情况就是矩形区域包含了黑块路径，这个特判以下即可。

然后答案就好求了，变成二维数点，主席树即可。复杂度 \(O(n\log n)\)。