题目链接
主要算法：
线段树（虚假的），奇技淫巧（真正的）
思路：
1.初步:考虑如何保证一个区间坐好后是一个矩形，有一个思路从另一个题中启示我们维护 \(xmin,xmax,ymin,ymax\) ,但是这样无法保证在中间挖一个空的情况（有一个别的题解，可以染色后维护四个角和一个判框的东西），但我们觉得就算可以维护这样一次修改会改动很多东西，不太好做。
2.进一步：所以引入一个染色，在第\(i\)的时间将第\(i\)个人染成黑色，这时图变成了黑白两色，所以考虑黑点和白点的性质。对于左上角的黑点它的上下都是白点且其它黑点如果一个矩形都不满足，对于每一个白点如果四联通有两个黑点，就会出现拐角，不是矩形。所以对于矩形，满足条件的黑白点总数是1（一个黑色点+0个白色点），就可以写出不交换时的程序.
int black(int x,int y)
{
int ans=zs+1;
for(int i=0;i<=1;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m)ans=min(ans,num(xx,yy));
}
return ans;
}//满足黑点要求的最晚时间，左上第一个黑点出现
int white(int x,int y)
{
int bb[5];
for(int i=0;i<=3;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m)bb[i]=num(xx,yy);
else bb[i]=zs+1;
}
sort(bb+0,bb+4);
return bb[1];
}//满足白点要求的最早时间,第二个黑点出现
void js(int h,int l,int i)
{
val[i]=val[i-1];
if(white(h,l)<i)val[i]--;
if(black(h,l)>i)val[i]++;
for(int j=0;j<=3;j++)
{
int x=h+dx[j],y=l+dy[j];
if(x>=1&&x<=n&&y>=1&&y<=m)
{
if(white(x,y)==i&&i<num(x,y))val[i]++;
if(black(x,y)==i&&i>num(x,y))val[i]--;
}
}
}
3.交换：刚才的做法就是因为不好维护交换而被暴毙。所以考虑交换\(u\),\(v\)有什么影响，一定只对四联通有变化。最多改 \(10\) 个点。改这十个点有贡献的时间，区间修改。所以用线段树维护一下即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,q,zs,kz[N],val[N],st[20];
#define bianhao(x,y) (x-1)*m+y
#define num(x,y) kz[bianhao(x,y)]
int dx[5]={-1,0,1,0},dy[5]={0,-1,0,1};
int black(int x,int y)
{
int ans=zs+1;
for(int i=0;i<=1;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m)ans=min(ans,num(xx,yy));
}
return ans;
}//满足黑点要求的最晚时间
int white(int x,int y)
{
int bb[5];
for(int i=0;i<=3;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m)bb[i]=num(xx,yy);
else bb[i]=zs+1;
}
sort(bb+0,bb+4);
return bb[1];
}//满足白点要求的最早时间
struct node
{
int h,l;
}a[N];
struct stu
{
int mn,cnt,lz;
}sh[N<<2];
void js(int h,int l,int i)
{
val[i]=val[i-1];
if(white(h,l)<i)val[i]--;//这个点变黑之前是满足条件的白点
if(black(h,l)>i)val[i]++;//这个点变黑之后是满足条件的黑点
for(int j=0;j<=3;j++)
{
int x=h+dx[j],y=l+dy[j];
if(x>=1&&x<=n&&y>=1&&y<=m)//一定要判边界
{
if(white(x,y)==i&&i<num(x,y))val[i]++;//它是白点的第二个出现的黑点，所以从现在开始是一个满足条件的白点
if(black(x,y)==i&&i>num(x,y))val[i]--;//它是黑点的第一个出现的左上角黑点，所以从现在开始不是一个满足条件的黑点
}
}
}
void update(int x)
{
sh[x].cnt=0;//直接清空
sh[x].mn=min(sh[x<<1].mn,sh[x<<1|1].mn);
if(sh[x<<1].mn==sh[x].mn)sh[x].cnt+=sh[x<<1].cnt;
if(sh[x<<1|1].mn==sh[x].mn)sh[x].cnt+=sh[x<<1|1].cnt;
return ;
}
void build(int x,int l,int r)
{
if(l==r)
{
sh[x].mn=val[l],sh[x].cnt=1;//最小值能否为0？不能，因为无论如何最左上的黑点一定符合黑点条件
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
update(x);
return ;
}
void pushdown(int x)
{
if(sh[x].lz==0)return;
sh[x<<1].lz+=sh[x].lz,sh[x<<1].mn+=sh[x].lz;
sh[x<<1|1].lz+=sh[x].lz,sh[x<<1|1].mn+=sh[x].lz;
sh[x].lz=0;
return;
}
void modify(int x,int l,int r,int lt,int rt,int val)
{
if(l>rt||r<lt||rt<lt)return;
if(l>=lt&&r<=rt)
{
sh[x].mn+=val;sh[x].lz+=val;
return ;
}
pushdown(x);
int mid=(l+r)>>1;
if(lt<=mid)modify(x<<1,l,mid,lt,rt,val);
if(rt>mid)modify(x<<1|1,mid+1,r,lt,rt,val);
update(x);
}
int main()
{
//ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
cin>>n>>m>>q;
zs=n*m;
for(int i=1;i<=zs;i++)
{
cin>>a[i].h>>a[i].l;
a[i].h+=1,a[i].l+=1;//下标从1开始
num(a[i].h,a[i].l)=i;//变黑的时间点
}
for(int i=1;i<=zs;i++)js(a[i].h,a[i].l,i);
build(1,1,zs);
for(int i=1;i<=q;i++)
{
int u,v,xx,cnt=0;cin>>u>>v;u+=1,v+=1;//不要忘记下标加一
if(u>v)swap(u,v);//确保u比v小
if(u==v){cout<<sh[1].cnt<<'\n';continue;}
st[++cnt]=u;
st[++cnt]=v;
for(int j=0;j<=3;j++)
{
int x=a[u].h+dx[j],y=a[u].l+dy[j];
if(x>=1&&x<=n&&y>=1&&y<=m)st[++cnt]=num(x,y);
x=a[v].h+dx[j],y=a[v].l+dy[j];
if(x>=1&&x<=n&&y>=1&&y<=m)st[++cnt]=num(x,y);
}
sort(st+1,st+cnt+1);
for(int j=1;j<=cnt;j++)
{
if(st[j]==st[j-1])continue;//去重不能计算两遍？
if((xx=white(a[st[j]].h,a[st[j]].l))<st[j])//交换u,v对满足条件的白点减少情况（不存在不算）
modify(1,1,zs,max(u,xx),min(v,st[j])-1,-1);//如果是v周围的点，将v换成u,只会增加区间不会减少区间,所以只考虑u周围的点。
//对u周围的u,v限制区间的话点u的贡献就是从u到st[j],v就是从v到st[j],但有可能不是由u，v限制的，所以取min，max
if((xx=black(a[st[j]].h,a[st[j]].l))>st[j])//交换u,v对满足条件的白点减少情况（不存在不算）
modify(1,1,zs,max(u,st[j]),min(v,xx)-1,-1);//如果是u周围的点，将u换成v,只会增加区间不会减少区间
//对v周围的区间，v的贡献是身体从st[j]到v,u的贡献就是从st[j]到u,
}
swap(num(a[u].h,a[u].l),num(a[v].h,a[v].l));swap(a[u],a[v]);
for(int j=1;j<=cnt;j++)
{
if(st[j]==st[j-1])continue;
if((xx=white(a[st[j]].h,a[st[j]].l))<st[j])modify(1,1,zs,max(u,xx),min(v,st[j])-1,1);
if((xx=black(a[st[j]].h,a[st[j]].l))>st[j])modify(1,1,zs,max(u,st[j]),min(v,xx)-1,1);
}
cout<<sh[1].cnt<<'\n';
}
return 0;
}