题解：P4898 [IOI 2018] seats 排座位
MatrixGroup
·
·
题解
题意
给定一个 H\times W 的格点的一个排列，Q 次询问，每次交换两个元素，查询有多少个前缀点的集合恰是一个长方形（内部的点）。
## 题解
设 $N=HW$。
先考虑一维的情况怎么做。这是经典的点减边容斥：一个集合是一个区间当且仅当其点数减去边（即，相邻的点对）数等于 $1$。并且若集合非空，这个值一定大于等于 $1$。（具体的，等于连通块数，不过在这个题里不重要）因此使用线段树维护每个前缀的该值的最小值和，修改就是对涉及设计点相邻的 $O(1)$ 个点、边，做后缀加、减即可。时间复杂度 $O(N+Q\log N)$。
考虑是否能扩展类似的容斥。对于点集 $S$（假定 $S$ 非空），记 $f(\cdot)$ 表示要求其中 $\texttt x$ 对应位置存在而其它位置没有限制的匹配数量。例如，上面对于一维情况的讨论就是统计 $f(\texttt{x})-f(\texttt{xx})=1$ 的前缀数量。如果 $f$ 的参数是 $O(1)$ 大小的网格，那么 $f$ 的相关是好维护的：对于其在网格中的每一次出现，都取其对应位置在序列中所出现位置的最大值，这一后缀带来了对应的贡献。而修改也是类似的，只涉及 $O(1)$ 个 $f$ 的修改。因此，假如有一些 $f$ 的线性组合，满足只有长方形能取到最小值，那么整个题目就可以在 $O(N+Q\log N)$ 的时间复杂度内完成。
考虑如何刻画长方形的特点。首先，对于一个长方形，恰有一个最左上角的点。如果用 $f$ 来刻画，稍微加强一下条件，就是说恰有一个点在无法向左或向上走（而且对于任意点集都至少有这么一个点）。使用容斥，可以得到条件是 $f(\texttt{x})-f(\texttt{xx})-f(\begin{matrix}\texttt x\\\texttt{x}\end{matrix})+f(\begin{matrix}\texttt { x}\\\texttt{xx}\end{matrix})=1$。类似的，对于四个方向都有这个条件。
分析一下这个条件意味着什么。对于每个可以向左或向上走的格点，通过不断走，一定可以走到唯一的这一个不能再走的点。不难推出四个角的点一定是一个长方形的顶点。那么从顶点往相邻的顶点一定存在路径，也就是这个长方形的边框是完整的。但是也就仅此而已了。
考虑还有什么长方形满足的条件，但是空心长方形不满足。可以发现，对于每个 $2\times 2$ 的网格，如果其一条对角线上都在长方形中，那么整个 $2\times 2$ 的部分都在长方形中。而且加上这个条件就可以保证是长方形！这是因为，从边框出发，可以一行一行向下证明，每一行都是满的。
综上所述，对于任何点集 $S$，有：
$$
\begin{cases}
f(\texttt{x})-f(\texttt{xx})-f(\begin{matrix}\texttt x\\\texttt{x}\end{matrix})+f(\begin{matrix}\texttt { x}\\\texttt{xx}\end{matrix})\ge 1\\
f(\texttt{x})-f(\texttt{xx})-f(\begin{matrix}\texttt x\\\texttt{x}\end{matrix})+f(\begin{matrix}\texttt {x }\\\texttt{xx}\end{matrix})\ge 1\\
f(\texttt{x})-f(\texttt{xx})-f(\begin{matrix}\texttt x\\\texttt{x}\end{matrix})+f(\begin{matrix}\texttt {xx}\\\texttt{x }\end{matrix})\ge 1\\
f(\texttt{x})-f(\texttt{xx})-f(\begin{matrix}\texttt x\\\texttt{x}\end{matrix})+f(\begin{matrix}\texttt {xx}\\\texttt{ x}\end{matrix})\ge 1\\
f(\begin{matrix}\texttt { x}\\\texttt{x }\end{matrix})-f(\begin{matrix}\texttt { x}\\\texttt{xx}\end{matrix})\ge 0\\
f(\begin{matrix}\texttt {x }\\\texttt{ x}\end{matrix})-f(\begin{matrix}\texttt {x }\\\texttt{xx}\end{matrix})\ge 0\\
f(\begin{matrix}\texttt { x}\\\texttt{x }\end{matrix})-f(\begin{matrix}\texttt {xx}\\\texttt{x }\end{matrix})\ge 0\\
f(\begin{matrix}\texttt {x }\\\texttt{ x}\end{matrix})-f(\begin{matrix}\texttt {xx}\\\texttt{ x}\end{matrix})\ge 0\\
\end{cases}
$$
且恰在 $S$ 为长方形时全部取等。把它们全都加起来并除以二可得
$$
2f(\texttt{x})-2f(\texttt{xx})-2f(\begin{matrix}\texttt x\\\texttt{x}\end{matrix})+f(\begin{matrix}\texttt { x}\\\texttt{x }\end{matrix})+f(\begin{matrix}\texttt {x }\\\texttt{ x}\end{matrix})\ge 2
$$
且恰在 $S$ 为长方形时全部取等。按照前文所述维护即可。
## 代码
```cpp
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,del##i##verme=int(n);i<del##i##verme;++i)
#define rep1(i,n) for(int i=1,parano##i##a=int(n);i<=parano##i##a;++i)
#define pb push_back
using namespace std;
struct segtree{
int ad[2222222],mn[2222222],cnt[2222222];
void build(int i,int l,int r,int *c)
{
ad[i]=0;
if(l==r)
{
mn[i]=c[l];cnt[i]=1;
}
else
{
int m=(l+r)>>1;
build(i<<1,l,m,c);build(i<<1|1,m+1,r,c);
if(mn[i<<1]==mn[i<<1|1]){mn[i]=mn[i<<1];cnt[i]=cnt[i<<1]+cnt[i<<1|1];}
else if(mn[i<<1]<mn[i<<1|1]){mn[i]=mn[i<<1];cnt[i]=cnt[i<<1];}
else {mn[i]=mn[i<<1|1];cnt[i]=cnt[i<<1|1];}
}
}
void add(int i,int il,int ir,int ql,int qr,int dt)
{
if(il>qr||ql>ir) return ;
if(ql<=il&&ir<=qr)
{
ad[i]+=dt;mn[i]+=dt;return ;
}
int m=(il+ir)>>1;
add(i<<1,il,m,ql,qr,dt);add(i<<1|1,m+1,ir,ql,qr,dt);
if(mn[i<<1]==mn[i<<1|1]){mn[i]=mn[i<<1];cnt[i]=cnt[i<<1]+cnt[i<<1|1];}
else if(mn[i<<1]<mn[i<<1|1]){mn[i]=mn[i<<1];cnt[i]=cnt[i<<1];}
else {mn[i]=mn[i<<1|1];cnt[i]=cnt[i<<1|1];}
mn[i]+=ad[i];
}
int query()
{
return (mn[1]==2)?cnt[1]:0;
}
};
segtree seg;
int h,w,q,a,b;
vector<int> vc[1000005];
int s[1000005],d[1000005];
const int dx[8]={0,0,1,-1,1,1,-1,-1};
const int dy[8]={1,-1,0,0,1,-1,1,-1};
const int vl[8]={-2,-2,-2,-2,1,1,1,1};
vector<int> pot;
void Clear(int x,int y)
{
rep(i,8)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>=0&&ny>=0&&nx<h&&ny<w)
{
int id=max(vc[x][y],vc[nx][ny]);
if(id==1145141919) continue;
pot.pb(id);
d[id]-=vl[i];
}
}
vc[x][y]=1145141919;
}
void Set(int x,int y,int vt)
{
vc[x][y]=vt;
rep(i,8)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>=0&&ny>=0&&nx<h&&ny<w)
{
int id=max(vc[x][y],vc[nx][ny]);
if(id==1145141919) continue;
pot.pb(id);
d[id]+=vl[i];
}
}
}
void Solve()
{
for(int x:pot)
{
if(d[x])
{
seg.add(1,1,h*w,x,h*w,d[x]);
d[x]=0;
}
}
pot.clear();
}
int x[1000005],y[1000005];
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);
cin>>h>>w>>q;
rep(i,h) vc[i]=vector<int>(w);
rep1(i,h*w)
{
cin>>x[i]>>y[i];vc[x[i]][y[i]]=i;
}
rep(i,h) rep(j,w)
{
if(i) ----s[max(vc[i][j],vc[i-1][j])];
if(j) ----s[max(vc[i][j],vc[i][j-1])];
if(i&&j) ++s[max(vc[i][j],vc[i-1][j-1])],++s[max(vc[i-1][j],vc[i][j-1])];
}
rep1(i,h*w) s[i]+=s[i-1]+2;
seg.build(1,1,h*w,s);
while(q--)
{
cin>>a>>b;++a;++b;swap(x[a],x[b]);swap(y[a],y[b]);
Clear(x[a],y[a]);Clear(x[b],y[b]);
Set(x[a],y[a],a);Set(x[b],y[b],b);
Solve();
cout<<seg.query()<<'\n';
}
return 0;
}
```