【2023武汉集训模拟赛03】嘉心糖 做题记录

有一个长为 $n$ 的序列 $a$，刚开始 $a_i=i$。还有一个 $n$ 个点的无向图 $G$，刚开始 $G$ 中没有边。

有 $m$ 个操作，每一次给定一个 $1\le x<n$ 的 $x$，在 $G$ 中连一条 $a_x$ 和 $a_{x+1}$ 之间的边，然后交换 $a_x$ 和 $a_{x+1}$。

求 $G$ 中的最大团的大小。

$1\le n,m\le 2\times 10^5$。

由于最大团等于补图的最大独立集，所以考虑补图。

不妨先给补图 $H$ 重定向，强制让编号小的连向编号大的，那么注意到 $H$ 中若有 $x\to y$，$y\to z$ 这两条边那么也一定有 $x\to z$ 这条边，即 $H$ 是一个偏序关系图。注意到偏序关系图的最大独立集等于最长反链，最长反链等于最小链覆盖，最小链覆盖可以通过把 $u$ 拆成入点和出点跑二分图最大匹配做，那么问题就转化为求 $H$ 的拆点二分图最大匹配。

考虑先贪心匹配，注意到若当前匹配了 $k$ 对点，那么所有度数 $>k$ 且未匹配的左部点一定能匹配。这一部分可以用 set 简单维护，时间复杂度 $O(n\log n)$。

最后停下来时有 $n-k$ 个左部点，它们的度数一定都 $\le k$，由于度数 $\le k$ 的点最多只有 $\lfloor\frac{m}{n-k}\rfloor$ 个，所以有 $n-k\le \sqrt m$ 即未匹配的点是 $O(\sqrt m)$ 的。那么用并查集维护一下匈牙利找边的过程即可。

时间复杂度 $O(n\log n+n\sqrt m)$。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>

using namespace std;

const int S=200005,mod=1145143;

int n,m;
int a[S];
vector<int> to[S];
set<int> st;
int tp,sta[S];
bool flg[S];
int blg[S],fa[S];

inline int read()
{
	int s=0,c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') s=s*10+c-48,c=getchar();
	return s;
}

int fnd(int x)
{
	return fa[x]==x?x:fa[x]=fnd(fa[x]);
}

bool dfs(int u)
{
	for(int v=fnd(u+1),i=-1;v<=n;v=fnd(v+1))
	{
		while(i+1<to[u].size()&&to[u][i+1]<=v) i++;
		if(i==-1||v!=to[u][i])
		{  
			int tmp=blg[v];
			blg[v]=u;
			fa[fnd(v)]=fnd(v+1);
			if(tmp==0||dfs(tmp)) return true;
			blg[v]=tmp;
		}
	}
	return false;
}

int main()
{
	freopen("sugar.in","r",stdin);
	freopen("sugar.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=i;
	for(int i=1;i<=m;i++)
	{
		int ix=read();
		int x=a[ix],y=a[ix+1];
		to[x].push_back(y),to[y].push_back(x);
		swap(a[ix],a[ix+1]);
	}
	for(int i=1;i<=n;i++)
	{
		sort(to[i].begin(),to[i].end());
		to[i].erase(unique(to[i].begin(),to[i].end()),to[i].end());
		vector<int> tmp;
		for(int j:to[i]) if(j>i) tmp.push_back(j);
		to[i]=tmp;
	}
	int ans=n;
	for(int i=1;i<=n;i++) st.insert(i);
	for(int i=1;i<=n;i++)
	{
		if(st.count(i)) st.erase(i);
		for(int v:to[i]) if(st.count(v)) st.erase(v),sta[++tp]=v;
		if(!st.empty())
		{
			blg[*st.begin()]=i,flg[i]=true,ans--;
			st.erase(st.begin());
		}
		while(tp>0) st.insert(sta[tp--]);
	}
	for(int i=1;i<=n;i++)
	{
		if(!flg[i])
		{
			for(int j=1;j<=n+1;j++) fa[j]=j;
			ans-=dfs(i);
		}
	}
	printf("%d\n",ans);
	return 0;
}