P3776 [APIO2017] 斑斓之地

洛谷
如果想到了还是比较好写的题目。
对于这种平面图统计有多少连通块可以往平面图欧拉公式考虑。
我们把每个方块看成一个点，如果两个块都没有被走过，就视为有边。
分析平面图欧拉公式推论：\(|V|-|E|+|F|=k+1\)。
其中 \(|V|\) 表示平面图中点的数量，\(|E|\) 表示平面图中边的数量，\(|F|\) 表示其中面的数量,而 \(k\) 表示的是其中的连通块数量，需要注意这里面的 \(|F|\) 是包含外部面的，如果不包含，那么就需要把右边的面去掉，在求解中显然去掉更方便。
对于 \(|V|\) 正难则反，先算出里面总共有多少个点，然后把其中被经过的点去掉即可，非常简单，直接二维数点即可。
对于 \(|E|\) 同理，我们只需要维护纵向边和横向边即可。
对于 \(|F|\) 则比较复杂。
考虑一下什么时候会形成一个面，分为两种情况（不包含外部面）。

• 原图上 \(2\times 2\) 的方格均没有被经过，形成一个面。
  
• \(2\times 2\) 的方格被部分破坏，但是靠向外连接最后形成了一个较大的面。
  

对于第一种情况，同样可以直接二维数点，记录每个点能否作为左上角即可，注意需要去重。
第二种情况，由于如果被破坏了而产生非 \(2\times 2\) 的结构，想要最后绕回来连成一个面就必须把河流包进去，也就是说只有在河流处于这个范围内时才可以有第二种情况，并且只有一个，如果有多个则其中一定有一个包含了其它面。
代码：
[code]#include#define int long longusing namespace std;int n,m,len,qq,sx,sy;char s[200005];vector e[200005][4];struct Q{        int op,l,r,id;};vector q[200005][4];int maxx,mixx=1e9,mayy,miyy=1e9;void add(int x,int y){        maxx=max(maxx,x),mixx=min(mixx,x);        mayy=max(mayy,y),miyy=min(miyy,y);        e[x][0].push_back(y);        e[x][1].push_back(y),e[x-1][1].push_back(y);        e[x][2].push_back(y-1),e[x][2].push_back(y);        e[x-1][3].push_back(y-1),e[x-1][3].push_back(y),e[x][3].push_back(y-1),e[x][3].push_back(y);}struct BT{        int c[200005];        int lowbit(int x){                return x&-x;        }        void add(int x,int y){                x++;                for(int i=x;ix&&maxxy&&mayy>n>>m>>len>>qq;        cin>>sx>>sy;        add(sx,sy);        for(int i=1;i>s;                if(s=='N')sx--;                else if(s=='S')sx++;                else if(s=='E')sy++;                else sy--;                add(sx,sy);        }        for(int i=1,x,y,xx,yy;i>x>>y>>xx>>yy;                add2(i,x,y,xx,yy);        }        for(int i=1;i