专栏文章

题解：P4898 [IOI 2018] seats 排座位

MMatrixGroup时序绚乱
P4898题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minchc8x
此快照首次捕获于
2025/12/02 00:09
3 个月前
此快照最后确认于
2025/12/02 00:09
3 个月前
查看原文

题意

给定一个 H×WH\times W 的格点的一个排列，QQ 次询问，每次交换两个元素，查询有多少个前缀点的集合恰是一个长方形（内部的点）。
HW≤106,Q≤5×104HW\le 10^6,Q\le 5\times 10^4，3s。

题解

设 N=HWN=HW。
先考虑一维的情况怎么做。这是经典的点减边容斥：一个集合是一个区间当且仅当其点数减去边（即，相邻的点对）数等于 11。并且若集合非空，这个值一定大于等于 11。（具体的，等于连通块数，不过在这个题里不重要）因此使用线段树维护每个前缀的该值的最小值和，修改就是对涉及设计点相邻的 O(1)O(1) 个点、边，做后缀加、减即可。时间复杂度 O(N+Qlog⁡N)O(N+Q\log N)。
考虑是否能扩展类似的容斥。对于点集 SS（假定 SS 非空），记 f(⋅)f(\cdot) 表示要求其中 x\texttt x 对应位置存在而其它位置没有限制的匹配数量。例如，上面对于一维情况的讨论就是统计 f(x)−f(xx)=1f(\texttt{x})-f(\texttt{xx})=1 的前缀数量。如果 ff 的参数是 O(1)O(1) 大小的网格，那么 ff 的相关是好维护的：对于其在网格中的每一次出现，都取其对应位置在序列中所出现位置的最大值，这一后缀带来了对应的贡献。而修改也是类似的，只涉及 O(1)O(1) 个 ff 的修改。因此，假如有一些 ff 的线性组合，满足只有长方形能取到最小值，那么整个题目就可以在 O(N+Qlog⁡N)O(N+Q\log N) 的时间复杂度内完成。
考虑如何刻画长方形的特点。首先，对于一个长方形，恰有一个最左上角的点。如果用 ff 来刻画，稍微加强一下条件，就是说恰有一个点在无法向左或向上走（而且对于任意点集都至少有这么一个点）。使用容斥，可以得到条件是 f(x)−f(xx)−f(xx)+f( xxx)=1f(\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×22\times 2 的网格，如果其一条对角线上都在长方形中，那么整个 2×22\times 2 的部分都在长方形中。而且加上这个条件就可以保证是长方形！这是因为，从边框出发，可以一行一行向下证明，每一行都是满的。
综上所述，对于任何点集 SS，有：
{f(x)−f(xx)−f(xx)+f( xxx)≥1f(x)−f(xx)−f(xx)+f(x xx)≥1f(x)−f(xx)−f(xx)+f(xxx )≥1f(x)−f(xx)−f(xx)+f(xx x)≥1f( xx )−f( xxx)≥0f(x  x)−f(x xx)≥0f( xx )−f(xxx )≥0f(x  x)−f(xx x)≥0\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}
且恰在 SS 为长方形时全部取等。把它们全都加起来并除以二可得
2f(x)−2f(xx)−2f(xx)+f( xx )+f(x  x)≥22f(\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
且恰在 SS 为长方形时全部取等。按照前文所述维护即可。

代码

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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...