CF1416D Graph and Queries 做题记录

给定一个 nn 个点 mm 条边的无向图,第 ii 个点的点权初始值为 pip_i,所有 pip_i 互不相同。

接下来进行 qq 次操作,分为两类:

  • 1 v\tt 1\ v 查询与 vv 连通的点中, pup_u 最大的点 uu 并输出 pup_u,然后让 pu=0p_u=0
  • 2 i\tt 2\ i 将第 ii 条边删掉。

1n21051 \le n \le 2 \cdot 10^51m31051 \le m \le 3 \cdot 10^51q51051 \le q \le 5 \cdot 10^5

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

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

具体的:

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

  2. 对于每一次询问操作,直接取对应连通块内权值最大的节点 uu(权值序列中第一个节点),把它的权值变为 00 之后放到权值序列的末尾即可;

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

用 set 维护连通块权值序列的时间复杂度是 O(logV)O(\log V) 的,其中 VV 是值域,又因为“启发式分裂”的时间复杂度是 (n+m)logn(n+m)\log n 的,所以时间复杂度 O((n+m)log2n+q)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;
}