【BZOJ2001】[HNOI2010]城市建设（CDQ分治，线段树分治）

时间：2023-03-24 23:50:25
【BZOJ2001】[HNOI2010]城市建设（CDQ分治，线段树分治）

【BZOJ2001】[HNOI2010]城市建设（CDQ分治，线段树分治）

题面

BZOJ

洛谷

题解

好神仙啊这题。原来想做一直不会做(然而YCB神仙早就切了），今天来怒写一发。

很明显这个玩意换种做法可以用线段树分治做，那么只需要\(LCT\)动态维护一下\(LCT\)就好了，时间复杂度？似乎是\(O(nlog^2m)\)的，每条边放在线段树上是一个\(log\)的，\(LCT\)还要一个\(log\)，然而常数十分大，大得一匹，洛谷上只能过\(80\)分。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 50050

#define ls (t[x].ch[0])

#define rs (t[x].ch[1])

#define lson (now<<1)

#define rson (now<<1|1)

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;

}

struct Line{int u,v,w;}E[MAX<<2];

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

vector<int> t[MAX<<2];

struct LCT

{

	struct Node{int ch[2],ff,rev,v,mx;}t[MAX<<2];

	int S[MAX<<2],top;

	bool isroot(int x){return t[t[x].ff].ch[0]!=x&&t[t[x].ff].ch[1]!=x;}

	void pushdown(int x){if(t[x].rev)t[ls].rev^=1,t[rs].rev^=1,t[x].rev=0,swap(ls,rs);}

	void pushup(int x)

		{

			t[x].mx=x;

			if(ls&&t[t[ls].mx].v>t[t[x].mx].v)t[x].mx=t[ls].mx;

			if(rs&&t[t[rs].mx].v>t[t[x].mx].v)t[x].mx=t[rs].mx;

		}

	void rotate(int x)

		{

			int y=t[x].ff,z=t[y].ff;

			int k=t[y].ch[1]==x;

			if(!isroot(y))t[z].ch[t[z].ch[1]==y]=x;t[x].ff=z;

			t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].ff=y;

			t[x].ch[k^1]=y;t[y].ff=x;

			pushup(y);pushup(x);

		}

	void Splay(int x)

		{

			S[top=1]=x;

			for(int i=x;!isroot(i);i=t[i].ff)S[++top]=t[i].ff;

			while(top)pushdown(S[top--]);

			while(!isroot(x))

			{

				int y=t[x].ff,z=t[y].ff;

				if(!isroot(y))

					(t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);

				rotate(x);

			}

		}

	int getroot(int x){access(x);Splay(x);while(ls)x=ls;return x;}

	void access(int x){for(int y=0;x;y=x,x=t[x].ff)Splay(x),rs=y,pushup(x);}

	void makeroot(int x){access(x);Splay(x);t[x].rev^=1;}

	void split(int x,int y){makeroot(x);access(y);Splay(y);}

	void cut(int x,int y){split(x,y);t[x].ff=t[y].ch[0]=0;pushup(y);}

	void link(int x,int y){makeroot(x);t[x].ff=y;}

	int Query(int x,int y){split(x,y);return t[y].mx;}

}T;

void Modify(int now,int l,int r,int L,int R,int x)

{

	if(L>R)return;

	if(L<=l&&r<=R){t[now].push_back(x);return;}

	int mid=(l+r)>>1;

	if(L<=mid)Modify(lson,l,mid,L,R,x);

	if(R>mid)Modify(rson,mid+1,r,L,R,x);

}

int SS[MAX<<2],st[MAX<<2];

ll Ans,ans[MAX];int Stop;

void Query(int now,int l,int r)

{

	//Add edge

	int ltop=Stop,mid=(l+r)>>1;

	for(int i=0,l=t[now].size();i<l;++i)

	{

		int p=t[now][i],u=E[p].u,v=E[p].v,w=E[p].w;

		if(T.getroot(u)==T.getroot(v))

		{

			int mx=T.Query(u,v);

			if(T.t[mx].v>w)

			{

				T.cut(E[mx-n].u,mx),T.cut(E[mx-n].v,mx),Ans-=E[mx-n].w;

				SS[++Stop]=mx-n;st[Stop]=1;

			}

			else continue;

		}

		T.link(p+n,u);T.link(p+n,v);Ans+=w;

		SS[++Stop]=p;st[Stop]=-1;

	}

	if(l==r)ans[l]=Ans;

	else Query(lson,l,mid),Query(rson,mid+1,r);

	for(int i=Stop;i>ltop;--i)

		if(st[i]<0)T.cut(SS[i]+n,E[SS[i]].u),T.cut(SS[i]+n,E[SS[i]].v),Ans-=E[SS[i]].w;

		else T.link(SS[i]+n,E[SS[i]].u),T.link(SS[i]+n,E[SS[i]].v),Ans+=E[SS[i]].w;

	Stop=ltop;

}

int pos[MAX],cnt;

int main()

{

	n=read();m=read();Q=read();cnt=m;

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

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

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

	{

		int k=read(),d=read(),x=pos[k];

		Modify(1,1,Q,L[k],i-1,x);L[k]=i;

		E[++cnt]=E[x];E[cnt].w=d;pos[k]=cnt;

	}

	for(int i=1;i<=cnt;++i)T.t[i+n].v=E[i].w;

	for(int i=1;i<=m;++i)Modify(1,1,Q,L[i],Q,pos[i]);

	Query(1,1,Q);

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

	return 0;

}

然而正解的\(CDQ\)分治太神仙了，以至于我花了很久才咕完这题。

思路很容易讲清楚：

每次考虑当前的所有边，我们考虑我们的分治区间，有些边会被修改，有些边不会被修改。会在区间内被修改的边我们显然只能递归处理，考虑不会被修改的边，那么这些边只有三种情况：第一种是必定在\(MST\)的边，那么这些边我们直接连上，这样子可以缩点。另外一种边是一定不会出现在\(MST\)的边，那么这种边我们直接丢掉就好了。还有一种是不知道的边，那么我们直接递归处理即可。

时间复杂度？不会证，听说两个\(log\)。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define ll long long

#define MAX 50050

#define inf 1e9

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;

}

struct Line{int u,v,w,id;}E[MAX],St[MAX],e[30][MAX],tmp[MAX];

bool operator<(Line a,Line b){return a.w<b.w;}

struct Query{int x,w;}q[MAX];

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

int f[MAX],c[MAX],cnt;

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

void init(int x)

{

	for(int i=1;i<=x;++i)f[tmp[i].u]=tmp[i].u;

	for(int i=1;i<=x;++i)f[tmp[i].v]=tmp[i].v;

}

int W[MAX],size[50];

void Contraction(int &z,ll &Ans)

{

	init(z);sort(&tmp[1],&tmp[z+1]);int top=0;

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

		if(getf(tmp[i].u)!=getf(tmp[i].v))

			f[getf(tmp[i].u)]=getf(tmp[i].v),St[++top]=tmp[i];

	for(int i=1;i<=top;++i)f[St[i].u]=St[i].u,f[St[i].v]=St[i].v;

	for(int i=1;i<=top;++i)//Get the edge must be used

		if(St[i].w>-inf)

			f[getf(St[i].u)]=getf(St[i].v),Ans+=St[i].w;

	top=0;

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

		if(getf(tmp[i].u)!=getf(tmp[i].v))//Get the edge may be used

		{

			St[++top]=tmp[i];

			c[tmp[i].id]=top;

			St[top].u=getf(tmp[i].u);

			St[top].v=getf(tmp[i].v);

		}

	z=top;for(int i=1;i<=top;++i)tmp[i]=St[i];

}

void Reduction(int &z)

{

	init(z);sort(&tmp[1],&tmp[z+1]);int top=0;

	for(int i=1;i<=z;++i)//Delete the edge will

		if(getf(tmp[i].u)!=getf(tmp[i].v))

			f[getf(tmp[i].u)]=getf(tmp[i].v),St[++top]=tmp[i],c[tmp[i].id]=top;

		else if(tmp[i].w>=inf)St[++top]=tmp[i],c[tmp[i].id]=top;

	z=top;for(int i=1;i<=top;++i)tmp[i]=St[i];

}

void CDQ(int l,int r,int dep,ll Ans)

{

	if(l==r)W[q[l].x]=q[l].w;//modify

	int z=size[dep],mid=(l+r)>>1;

	for(int i=1;i<=z;++i)e[dep][i].w=W[e[dep][i].id];

	for(int i=1;i<=z;++i)tmp[i]=e[dep][i],c[tmp[i].id]=i;

	if(l==r)//Get MST

	{

		init(z);sort(&tmp[1],&tmp[z+1]);

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

			if(getf(tmp[i].u)!=getf(tmp[i].v))

				f[getf(tmp[i].u)]=getf(tmp[i].v),Ans+=tmp[i].w;

		ans[l]=Ans;return;

	}

	for(int i=l;i<=r;++i)tmp[c[q[i].x]].w=-inf;

	Contraction(z,Ans);

	for(int i=l;i<=r;++i)tmp[c[q[i].x]].w=+inf;

	Reduction(z);

	for(int i=1;i<=z;++i)e[dep+1][i]=tmp[i];size[dep+1]=z;

	CDQ(l,mid,dep+1,Ans);CDQ(mid+1,r,dep+1,Ans);

}

int main()

{

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

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

	for(int i=1;i<=Q;++i)q[i].x=read(),q[i].w=read();

	for(int i=1;i<=m;++i)W[i]=E[i].w;

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

	size[0]=m;CDQ(1,Q,0,0);

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

	return 0;

}

相关文章