题目
越写越短的LCT
我们可以把树转化成两个限制：
(1.)无环。
(2.|E|=|V|-1)。
很显然第一个限制看上去比第二个好做，所以我们先搞第一个。
容易知道如果一段区间([l,r])形成的图（我们成为生成图）如果有环，那么包含([l,r])的区间的生成图一定有环。
我们要求每个左端点(l)求出其最大能扩展到的右端点(r)。由于上面的结论，这个(r)一定单调递增。
所以我们可以用双指针来搞。而加边删边判断有没有环则可以用LCT来搞。
这样我们就解决了第一个限制，然后来搞第二个。
我们考虑维护这样一个东西：确定了左端点(l)时，以(i)为右端点的区间的(|V|-|E|)，记做(f_i)。
先不管这个东西怎么维护，假如我们能够维护这个东西，那么我们查询的就是([l,r])内（(r)为上面求的那个最大能扩展到的右端点）(f=1)的数量。
然后我们连边删边就是区间加。
这东西乍一看是没法做的，但是注意到由于第一个限制，我们是不会出现环的，也就是说(|V|-|E|ge1)，那么我们就可以只要维护区间最小值的数量了。
这东西就可以直接线段树来做了。
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
namespace IO
{
char ibuf[(1<<21)+1],*iS,*iT;
char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
int read(){int x=0,c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;}
}using IO::read;
const int N=2007,M=200007;
int n,m;
namespace Graph
{
int f[N][N],dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
vector<int>E[M];
void buildG()
{
for(int i=1,j;i<=n;++i)for(j=1;j<=m;++j) f[i][j]=read();
for(int i=1,j,k,x,y;i<=n;++i)
for(j=1;j<=m;++j)
for(k=0;k<4;++k)
{
x=i+dx[k],y=j+dy[k];
if(x>=1&&x<=n&&y>=1&&y<=m) E[f[i][j]].pb(f[x][y]);
}
}
}using namespace Graph;
namespace LCT
{
int fa[M],ch[M][2],rev[M];
#define lc ch[x][0]
#define rc ch[x][1]
int nroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
void pushrev(int x){swap(lc,rc),rev[x]^=1;}
void pushdown(int x){if(!rev[x])return ;rev[x]=0,pushrev(lc),pushrev(rc);}
void pushall(int x){if(nroot(x))pushall(fa[x]);pushdown(x);}
void rotate(int x)
{
int y=fa[x],z=fa[y],k=ch[y][1]==x;
if(nroot(y)) ch[z][ch[z][1]==y]=x;
fa[x]=z,fa[ch[x][!k]]=y,ch[y][k]=ch[x][!k],fa[y]=x,ch[x][!k]=y;
}
void splay(int x)
{
pushall(x);
for(int y;nroot(x);rotate(x)) if(nroot(y=fa[x])) rotate((ch[fa[y]][0]==y)^(ch[y][0]==x)? x:y);
}
void access(int x){for(int y=0;x;x=fa[y=x])splay(x),rc=y;}
void makeroot(int x){access(x),splay(x),pushrev(x);}
int findroot(int x){access(x),splay(x);while(lc)x=lc;return splay(x),x;}
int link(int x,int y){return makeroot(x),findroot(y)==x? 0:fa[x]=y;}
void cut(int x,int y){makeroot(x);if(findroot(y)==x&&fa[y]==x&&!ch[y][0]) fa[y]=ch[x][1]=0;}
#undef lc
#undef rc
}using namespace LCT;
namespace SegTree
{
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
int mn[M<<2],sum[M<<2],tag[M<<2];
void pushup(int p)
{
if(mn[ls]<mn[rs]) mn[p]=mn[ls],sum[p]=sum[ls];
if(mn[rs]<mn[ls]) mn[p]=mn[rs],sum[p]=sum[rs];
if(mn[ls]==mn[rs]) mn[p]=mn[ls],sum[p]=sum[ls]+sum[rs];
}
void modify(int p,int v){mn[p]+=v,tag[p]+=v;}
void pushdown(int p){modify(ls,tag[p]),modify(rs,tag[p]),tag[p]=0;}
void buildS(int p,int l,int r)
{
if(l==r) return (void)(sum[p]=1);
buildS(ls,l,mid),buildS(rs,mid+1,r),pushup(p);
}
void update(int p,int l,int r,int L,int R,int x)
{
if(L<=l&&r<=R) return modify(p,x);
if(tag[p]) pushdown(p);
if(L<=mid) update(ls,l,mid,L,R,x);
if(R>mid) update(rs,mid+1,r,L,R,x);
pushup(p);
}
int query(int p,int l,int r,int L,int R)
{
if(L<=l&&r<=R) return mn[p]==1? sum[p]:0;
if(tag[p]) pushdown(p);
return (L<=mid? query(ls,l,mid,L,R):0)+(R>mid? query(rs,mid+1,r,L,R):0);
}
#undef ls
#undef rs
#undef mid
}using namespace SegTree;
int main()
{
ll ans=0;int l=1,r=0,S;
n=read(),m=read(),buildG(),buildS(1,1,S=n*m);
for(int f,c;l<=S;++l)
{
for(;r<S;)
{
f=c=0,++r;
for(int v:E[r]) if(v<=r&&v>=l&&!link(v,r)) {f=1;break;}
for(int v:E[r]) cut(v,r);
if(f==1) {--r;break;}
for(int v:E[r]) if(v<=r&&v>=l) link(v,r),++c;
update(1,1,S,r,r,r-l+1),update(1,1,S,r,S,-c);
}
ans+=query(1,1,S,l,r);
for(int v:E[l]) if(v<=r&&v>=l) cut(v,l),update(1,1,S,v,S,1);
update(1,1,S,l,r,-1);
}
printf("%lld",ans);
}