CF1416D Graph and Queries 做题记录

给定一个 $n$ 个点 $m$ 条边的无向图，第 $i$ 个点的点权初始值为 $p_i$,所有 $p_i$ 互不相同。

接下来进行 $q$ 次操作，分为两类：

• $\tt 1\ v$ 查询与 $v$ 连通的点中， $p_u$ 最大的点 $u$ 并输出 $p_u$，然后让 $p_u=0$。
• $\tt 2\ i$ 将第 $i$ 条边删掉。

$1 \le n \le 2 \cdot 10^5$，$1 \le m \le 3 \cdot 10^5$，$1 \le q \le 5 \cdot 10^5$。

这是一道比较有趣的“启发式分裂”题。

首先容易发现，每次删边之后大小较小的那部分的大小至少减半，那么参照启发式合并的思路，考虑每次断边之后在大小较小的部分上跑一次 dfs，求出上次断边到这次断边之间的询问的答案。

具体的：

1. 首先对图上的每个连通块都跑一遍 dfs，求出它们内部节点按照权值从大到小排序之后的序列。并且把所有删边操作倒过来，变成加边操作，用并查集找到所有改变图的连通性的删边操作；

2. 对于每一次询问操作，直接取对应连通块内权值最大的节点 $u$（权值序列中第一个节点），把它的权值变为 $0$ 之后放到权值序列的末尾即可；

3. 对于每一次删边操作，若这次操作不改变图的连通性，直接删掉它即可；否则删掉它之后在大小较小的那一部分上跑一次 dfs，求出它内部节点排序后的序列，根据这个序列和连通块分裂之前的序列就可以求出另一部分的序列。

用 set 维护连通块权值序列的时间复杂度是 $O(\log V)$ 的，其中 $V$ 是值域，又因为“启发式分裂”的时间复杂度是 $(n+m)\log n$ 的，所以时间复杂度 $O((n+m)\log^2 n+q)$，卡一卡可以过。

代码如下：（卡常用的火车头省略了）

#include <cstdio>
#include <vector>
#include <set>

using namespace std;

char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	return x*f;
}
void print(int x)
{
    if(x>9) print(x/10);
    *O++=x%10|48;
}

const int MS=200005,S=300005,QS=500005;

struct edge
{
	int x,y;
	bool del; // 是否被删除
}ed[S];

struct opt
{
	int tpe,id; // 操作类型，删边的编号/节点编号
	bool imp;
	int mnx; // 删边之后属于大小较小的连通块的点
}que[QS];

int n,m,q,qdel;
int a[MS];
vector<int> g[MS];
int fa[MS],siz[MS];
set<pair<int,int> > st[MS];
int cnt,uid[MS];

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

void dfs(int u,int stid)
{
	st[stid].erase(make_pair(-a[u],u));
	st[uid[u]].insert(make_pair(-a[u],u));
	for(int i:g[u])
	{
		if(ed[i].del) continue;
		int v=ed[i].x==u?ed[i].y:ed[i].x;
		if(uid[v]==uid[u]) continue;
		uid[v]=uid[u];
		dfs(v,stid);
	}
}

int main()
{
	n=rd();
	m=rd();
	q=rd();
	for(register int i=1;i<=n;++i) a[i]=rd();
	for(register int i=1;i<=m;++i)
	{
		ed[i].x=rd();
		ed[i].y=rd();
		g[ed[i].x].push_back(i),g[ed[i].y].push_back(i);
	}
	for(register int i=1;i<=q;++i)
	{
		que[i].tpe=rd();
		que[i].id=rd();
		if(que[i].tpe==2) ed[que[i].id].del=true;
	}
	for(register int i=1;i<=n;++i) siz[i]=(fa[i]=i)==i;
	for(register int i=1;i<=m;++i)
	{
		if(!ed[i].del)
		{
			int rx=fnd(ed[i].x),ry=fnd(ed[i].y);
			if(rx!=ry) fa[rx]=ry,siz[ry]+=siz[rx];
		}
	}
	for(register int i=q;i>=1;--i)
	{
		if(que[i].tpe==2)
		{
			int rx=fnd(ed[que[i].id].x),ry=fnd(ed[que[i].id].y);
			if(rx!=ry)
			{
				que[i].imp=true;
				if(siz[rx]<siz[ry]) que[i].mnx=ed[que[i].id].x;
				else que[i].mnx=ed[que[i].id].y;
				fa[rx]=ry,siz[ry]+=siz[rx];
				ed[que[i].id].del=false;
			}
		}
	}
	for(register int i=1;i<=n;++i) if(fa[i]==i) uid[i]=++cnt;
	for(register int i=1;i<=n;++i) st[uid[i]=uid[fnd(i)]].insert(make_pair(-a[i],i));
	for(register int i=1;i<=q;++i)
	{
		if(que[i].tpe==1)
		{
			int id=uid[que[i].id];
			pair<int,int> fir=*st[id].begin();
			print(-fir.first);
			*O++='\n';
			st[id].erase(fir);
			a[fir.second]=0;
			st[id].insert(make_pair(0,fir.second));
		}
		else
		{
			ed[que[i].id].del=true;
			if(que[i].imp)
			{
				uid[que[i].mnx]=++cnt;
				int oth=uid[ed[que[i].id].x==que[i].mnx?ed[que[i].id].y:ed[que[i].id].x];
				dfs(que[i].mnx,oth);
			}
		}
		if(O-obuf>(1<<22)) fwrite(obuf,O-obuf,1,stdout),O=obuf;
	}
	fwrite(obuf,O-obuf,1,stdout);
	return 0;
}