P5385 [Cnoi2019]须臾幻境(LCT+主席树，思维题)

题目

P5385 [Cnoi2019]须臾幻境

做法

考虑一条边\((u,v)\)是否\([L,R]\)中的贡献：\([L,R]\)中第一条位于\(u,v\)链的边，则减少了一个联通块

实现：\(LCT\)维护最小边，产生环则删除最小边，再替换\((\)和这题差不多\()\)

得出删除序列，建好主席树，直接查询\([L,R]\)中小于\(L\)的数量即可

Code

#include<bits/stdc++.h>

typedef int LL;

inline LL Read(){

	LL x(0),f(1); char c=getchar();

	while(c<'0' || c>'9'){

		if(c=='-') f=-1; c=getchar();

	}

	while(c>='0' && c<='9'){

		x=(x<<3)+(x<<1)+c-'0'; c=getchar();

	}return x*f;

}

const LL maxn=1e6+9,inf=0x3f3f3f3f;

LL n,m,q,seed;

LL ear[maxn];

namespace LCT{

	struct node{

		LL u,v;

	}e[maxn];

	LL son[maxn][2],fa[maxn],mi[maxn],mi_n[maxn],val[maxn],sta[maxn],r[maxn];

	inline LL Notroot(LL x){

		return son[fa[x]][0]==x || son[fa[x]][1]==x;

	}

	inline void Update(LL x){

		LL lt(son[x][0]),rt(son[x][1]);

		mi[x]=std::min(mi[lt],mi[rt]);

		if(mi[x]==mi[lt]){

			mi_n[x]=mi_n[lt];

		}else{

			mi_n[x]=mi_n[rt];

		}

		if(val[x]<=mi[x]){

			mi[x]=val[x]; mi_n[x]=x;

		}

	}

	inline void Pushr(LL x){

		std::swap(son[x][0],son[x][1]); r[x]^=1;

	}

	inline void Pushdown(LL x){

		if(r[x]){

			if(son[x][0]) Pushr(son[x][0]);

			if(son[x][1]) Pushr(son[x][1]);

			r[x]=0;

		}

	}

	inline void Rotate(LL x){

		LL y(fa[x]),z(fa[y]),lz(son[y][1]==x);

		if(Notroot(y)) son[z][son[z][1]==y]=x;

		son[y][lz]=son[x][lz^1]; fa[son[y][lz]]=y;

		son[x][lz^1]=y; fa[y]=x;fa[x]=z;

		Update(y); Update(x);

	}

	inline void Splay(LL x){

		LL y(x),tot(0);

		sta[++tot]=y;

		while(Notroot(y)) sta[++tot]=y=fa[y];

		while(tot) Pushdown(sta[tot--]);

		while(Notroot(x)){

			y=fa[x];

			if(Notroot(y)){

				LL z(fa[y]);

				if((son[y][0]==x)^(son[z][0]==y)) Rotate(x); else Rotate(y);

			}Rotate(x);

		}

	}

	inline void Access(LL x){

		for(LL y=0;x;y=x,x=fa[x]){

			Splay(x); son[x][1]=y; Update(x);

		}

	}

	inline void Makeroot(LL x){

		Access(x); Splay(x); Pushr(x);

	}

	inline void Split(LL x,LL y){

		Makeroot(x); Access(y); Splay(y);

	}

	inline LL Query(LL x,LL y){

		Split(x,y); return mi_n[y];

	}

	inline LL Find(LL x){

		Access(x); Splay(x);

		while(son[x][0]){

			Pushdown(x); x=son[x][0];

		}Splay(x);

		return x;

	}

	inline void Cut(LL x,LL y){

		Split(x,y); son[y][0]=fa[x]=0; Update(y);//这里也可不更新，因为在查询时整条链都会更新

	}

	inline void Link(LL x,LL y){

		Makeroot(x); fa[x]=y;

	}

	inline void Solve(){

		for(LL i=0;i<=n;++i) val[i]=mi[i]=inf,mi_n[i]=i;

		LL tot=n;

		for(LL i=1;i<=m;++i){

			LL u(Read()),v(Read());

			e[i]=(node){u,v};

			if(u==v){

				ear[i]=i; continue;

			}else if(Find(u)==Find(v)){

				LL t(Query(u,v)),x(val[t]); ear[i]=x;

				Cut(e[x].u,t); Cut(e[x].v,t);

			}

			++tot; mi[tot]=val[tot]=i; mi_n[tot]=tot;

			Link(u,tot); Link(v,tot);

		}

	}

}

namespace Sgt{

	LL nod;

	LL size[maxn*20],son[maxn*20][2],root[maxn];

	void Update(LL pre,LL &now,LL l,LL r,LL v){

		now=++nod; size[now]=size[pre]+1;

		if(l==r) return;

		LL mid(l+r>>1);

		if(v<=mid){

			Update(son[pre][0],son[now][0],l,mid,v);

			son[now][1]=son[pre][1];

		}else{

			Update(son[pre][1],son[now][1],mid+1,r,v);

			son[now][0]=son[pre][0];

		}

	}

	LL Query(LL pre,LL now,LL l,LL r,LL v){

		if(l==r) return size[now]-size[pre];

		LL mid(l+r>>1);

		if(mid<v) return Query(son[pre][1],son[now][1],mid+1,r,v)+size[son[now][0]]-size[son[pre][0]];

		else return Query(son[pre][0],son[now][0],l,mid,v);

	}

	inline void Solve(){

		for(LL i=1;i<=m;++i) Update(root[i-1],root[i],0,m,ear[i]);

		LL lst(0);

		while(q--){

			LL l(Read()),r(Read());

			if(seed>0)

			    l=1ll*(l+1ll*seed*lst%m)%m+1,

				r=1ll*(r+1ll*seed*lst%m)%m+1;

			if(l>r) std::swap(l,r);

			printf("%d\n",lst=n-Query(root[l-1],root[r],0,m,l-1));

		}

	}

}

int main(){

	n=Read(); m=Read(); q=Read(); seed=Read();

	LCT::Solve();

	Sgt::Solve();

	return 0;

}

巴特西

P5385 [Cnoi2019]须臾幻境(LCT+主席树，思维题)

题目

做法

Code

最新文章

热门文章