题意

给定 矩阵，求所有四联通区域的大小和、满足其中每个元素都小于所有其四联通的、相邻的、不在该区域的元素，并且该区域以外的矩阵是八联通的（包括 矩阵以外的超平面）。

思路

首先小于的条件可以通过由小到大加点解决，这样问题在于加点之后求两个区域内部是否联通。

其实看到八联通要包括矩阵以外的超平面就应该想到平面图欧拉定理的 然鹅我并没有。

这样我们直接使用并查集，维护点数，边数，以及联通快内部形成的小区域的数量，通过 即可解出剩下区域的数量，若合法应当为 。

CODE

#include<tuple>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define get(x,y) ((x-1)*n+y)
using namespace std;
using ll=long long;
const int N=760,M=1000010,FSIZE=1<<26,fx[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,s[N*N][4];
ll ans;
pair<int,int> e[M];
bool a[N][N];
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    for(;48>*InF||*InF>57;++InF);
    for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
}
int root(int x){
    if(s[x][0]){
        int r=s[x][0]=root(s[x][0]);
        s[r][1]+=s[x][1];
        s[r][2]+=s[x][2];
        s[r][3]+=s[x][3];
        s[x][1]=s[x][2]=s[x][3]=0;
        return(s[x][0]);
    }
    return(x);
}
void merge(int x,int y){
    if((x=root(x))!=(y=root(y))){
        s[x][0]=y;
        s[y][1]+=s[x][1];
        s[y][2]+=s[x][2];
        s[y][3]+=s[x][3];
        s[x][1]=s[x][2]=s[x][3]=0;
    }
}
int main(){
    freopen("valleys.in","r",stdin);
    freopen("valleys.out","w",stdout);
    fread(BuF,1,FSIZE,stdin);
    read(n);
    for(int i=1;i<=n;++i)
        for(int j=1,x;j<=n;++j){
            read(x);
            e[x]=make_pair(i,j);
        }
    for(int i=1;i<M;++i)
        if(e[i].first){
            int x=e[i].first,y=e[i].second,t=get(x,y);
            a[x][y]=1;
            s[t][1]=1;
            s[t][2]=a[x-1][y]+a[x+1][y]+a[x][y-1]+a[x][y+1];
            s[t][3]=(a[x-1][y]&&a[x][y-1]&&a[x-1][y-1])+
                    (a[x-1][y]&&a[x][y+1]&&a[x-1][y+1])+
                    (a[x+1][y]&&a[x][y-1]&&a[x+1][y-1])+
                    (a[x+1][y]&&a[x][y+1]&&a[x+1][y+1]);
            if(a[x-1][y]) merge(get(x-1,y),t);
            if(a[x][y-1]) merge(get(x,y-1),t);
            if(a[x+1][y]) merge(get(x+1,y),t);
            if(a[x][y+1]) merge(get(x,y+1),t);
            if(2+s[t][2]-s[t][3]-s[t][1]==1) ans+=s[t][1];
        }
    printf("%lld\n",ans);
    fclose(stdin);
    fclose(stdout);
    return(0);
}