【LOJ#3145】[APIO2019]桥梁（分块，并查集）

题面

题解

因为某个\(\text{subtask}\)没判\(n=1\)的情况导致我自闭了很久的题目。。。

如果没有修改操作，可以克鲁斯卡尔重构树在线处理。或者按照边权排序离线并查集处理。

现在有修改操作，于是我们来分块。

我们对于操作分块，每\(B\)个操作作为一组处理。不同组之间显然影响不大。

所以我们只需要处理同一组的就好了。

把边分成两类，一类是不会被修改的，这些边直接排序做前面的并查集就好了，这部分复杂度是\(O(m\frac{n}{B})\)的。另外一类是会被修改的，对于每次询问，我们暴力扫所有会被修改的边，看看是否可以加入进来，因此块内的修改边数不会超过\(B\)，所以这一部分是\(O(\frac{n}{B}B^2)=O(nB)\)的，但是还要支持并查集的撤销，所以多一个\(log\)，所以是\(O(nBlogn)\)的。

均摊一下取\(B=\sqrt {m logn}\)？？？

注意几个细节，前半部分那里分析复杂度的时候没有带\(log\)，所以用归并排序。

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAX 100100

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

const int BLK=500;

struct Edge{int u,v,w,i;}e[MAX],E[MAX],tmpE[MAX];

bool operator<(Edge a,Edge b){if(a.w!=b.w)return a.w>b.w;return a.i<b.i;}

bool cmpi(Edge a,Edge b){return a.i<b.i;}

int n,m,Q,ans[MAX];

int f[MAX],sz[MAX];

int getf(int x){return x==f[x]?x:getf(f[x]);}

struct dsuopt{int u,v;}St[MAX];int top;

void Merge(int u,int v)

{

	u=getf(u);v=getf(v);

	if(u==v)return;

	if(sz[u]<sz[v])swap(u,v);

	f[v]=u;sz[u]+=sz[v];

	St[++top]=(dsuopt){u,v};

}

void Cancel(){int u=St[top].u,v=St[top].v;--top;f[v]=v;sz[u]-=sz[v];}

struct Opt{int id,t,b,r;}q[MAX],tmp1[MAX],tmp2[MAX];int tot,t1,t2;

bool cmpb(Opt a,Opt b){return a.b>b.b;}

int vis[MAX],id[MAX],d[MAX];

void Work()

{

	for(int i=1;i<=m;++i)vis[i]=false;

	for(int i=1;i<=n;++i)f[i]=i,sz[i]=1;

	t1=t2=top=0;

	for(int i=1;i<=tot;++i)

		if(q[i].t==1)++t1,vis[q[i].b]=true,tmp1[t1]=q[i];

		else tmp2[++t2]=q[i];

	sort(&tmp2[1],&tmp2[t2+1],cmpb);

	for(int i=1;i<=m;++i)id[e[i].i]=i;

	for(int i=1,p=1;i<=t2;++i)

	{

		while(p<=m&&e[p].w>=tmp2[i].b)

		{

			if(!vis[e[p].i])Merge(e[p].u,e[p].v);

			++p;

		}

		int ltop=top;

		for(int j=1;j<=t1;++j)d[tmp1[j].b]=e[id[tmp1[j].b]].w;

		for(int j=1;j<=t1;++j)

			if(tmp1[j].id<tmp2[i].id)

				d[tmp1[j].b]=tmp1[j].r;

		for(int j=1;j<=t1;++j)

			if(d[tmp1[j].b]>=tmp2[i].b)

				Merge(e[id[tmp1[j].b]].u,e[id[tmp1[j].b]].v);

		ans[tmp2[i].id]=sz[getf(tmp2[i].r)];

		while(top>ltop)Cancel();

	}

	for(int i=1;i<=t1;++i)e[id[tmp1[i].b]].w=tmp1[i].r;

	t1=t2=0;

	for(int i=1;i<=m;++i)

		if(vis[e[i].i])E[++t1]=e[i];

		else e[++t2]=e[i];

	sort(&E[1],&E[t1+1]);

	merge(&e[1],&e[t2+1],&E[1],&E[t1+1],&tmpE[1]);

	for(int i=1;i<=m;++i)e[i]=tmpE[i];

}

int main()

{

	n=read();m=read();

	for(int i=1;i<=m;++i)e[i].u=read(),e[i].v=read(),e[i].w=read(),e[i].i=i;

	sort(&e[1],&e[m+1]);

	Q=read();

	for(int i=1;i<=Q;++i)

	{

		int t=read(),b=read(),r=read();if(t==2)swap(b,r);

		q[++tot]=(Opt){i,t,b,r};

		if(tot==BLK)Work(),tot=0;

	}

	if(tot)Work();

	for(int i=1;i<=Q;++i)if(ans[i])printf("%d\n",ans[i]);

	return 0;

}

巴特西

【LOJ#3145】[APIO2019]桥梁（分块，并查集）

【LOJ#3145】[APIO2019]桥梁（分块，并查集）

题面

题解

最新文章

热门文章