自动搬运

查看原文

来自洛谷，原作者为

	zhlzt Light in the eyes.

搬运于2025-08-24 22:10:14，当前版本为作者最后更新于2025-07-29 11:16:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

:::info[喜提洛谷当前最优解]{open} 原因大概是可持久化线段树维护方式与多数题解有所不同。

https://www.luogu.com.cn/record/227639843 :::

注意到有一个经典的 Trick：连通块数 = 点数 - 生成森林边数。

考虑 LCT 维护生成森林。

为了保证 $l\sim r$ 构成的图一定存在一个生成森林是我们构造的 $1\sim r$ 的生成森林的子图，需要令 $1\sim r$ 的生成森林中边的编号尽可能大。

于是，我们依次添加编号为 $1\sim m$ 的每条边，如果此前已连通则删除二点路径上编号最小的边。

为了维护路径上边的编号的最小值，我们可以使用拆边。新建结点表示该边，并令其点权为边的编号，同时分别与两个端点连边。

询问时，我们只需求出 $l\sim r$ 有多少边在构造的 $1\sim r$ 的生成森林中。使用可持久化线段树维护即可。

注意到每条边都会被加入，为了减小常数，我们直接维护 $1\sim r$ 的删边情况，删掉为 $1$，不删为 $0$。

设编号 $l\sim r$ 的边有 $c$ 条不在 $1\sim r$ 的生成森林中。则答案为 $n-(r-l+1-c)$。

时间复杂度 $\mathcal{O}(n+m\log n+(m+q)\log m)$，空间复杂度 $\mathcal{O}(n+m \log m)$。

:::success[[Cnoi2019] 须臾幻境 - P5385.cpp]

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5,maxm=2e5+5;
int root[maxn],tree[maxm<<4],ch[maxn<<4][2];
int sum[maxn],fath[maxn],tag[maxn],val[maxn],son[maxn][2];
int secu[maxm],secv[maxm],n,m,q,t,idx;
inline bool dir(int u){
	return son[fath[u]][1]==u;
}
inline bool isroot(int u){
	return son[fath[u]][0]!=u and son[fath[u]][1]!=u;
}
inline void pushup(int u){
	sum[u]=min(min(sum[son[u][0]],sum[son[u][1]]),val[u]);
}
inline void pushdown(int u){
	if(tag[u]){
		if(son[u][0]){
			tag[son[u][0]]^=1;
			swap(son[son[u][0]][0],son[son[u][0]][1]);
		}
		if(son[u][1]){
			tag[son[u][1]]^=1;
			swap(son[son[u][1]][0],son[son[u][1]][1]);
		}
		tag[u]=0;
	}
}
void update(int u){
	if(!isroot(u)) update(fath[u]);
	pushdown(u);
}
inline void rotate(int u){
	int p=fath[u],g=fath[p],d=dir(u);
	if(!isroot(p)) son[g][dir(p)]=u;
	son[p][d]=son[u][d^1],fath[son[u][d^1]]=p;
	son[u][d^1]=p,fath[p]=u,fath[u]=g;
	pushup(p),pushup(u);
}
inline void splay(int u){
	update(u);
	for(int p=fath[u];!isroot(u);rotate(u),p=fath[u]){
		if(!isroot(p)) rotate(dir(u)==dir(p)?p:u);
	}
}
inline int access(int u){
	int p=0;
	for(;u;p=u,u=fath[u]){
		splay(u),son[u][1]=p,pushup(u);
	}
	return p;
}
inline void makeroot(int u){
	int p=access(u);
	tag[p]^=1;
	swap(son[p][0],son[p][1]);
}
inline int find(int u){
	access(u),splay(u),pushdown(u);
	while(son[u][0]) pushdown(u=son[u][0]);
	splay(u);
	return u;
}
inline void split(int u,int v){
	makeroot(u),access(v),splay(v);
}
inline void link(int u,int v){
	makeroot(u),splay(u),fath[u]=v;
}
inline void cut(int u,int v){
	makeroot(u),access(v),splay(v);
	son[v][0]=fath[u]=0;
	pushup(v);
}
int build(int pos,int val,int p,int pl,int pr){
	int now=++idx;
	if(pl==pr){
		tree[now]=val;
		return now;
	}
	int mid=(pl+pr)>>1;
	if(pos<=mid) ch[now][0]=build(pos,val,ch[p][0],pl,mid),ch[now][1]=ch[p][1];
	else ch[now][1]=build(pos,val,ch[p][1],mid+1,pr),ch[now][0]=ch[p][0];
	tree[now]=tree[ch[now][0]]+tree[ch[now][1]];
	return now;
}
int query(int pos,int p,int pl,int pr){
	if(pos<=pl) return tree[p];
	int mid=(pl+pr)>>1;
	if(pos<=mid) return query(pos,ch[p][0],pl,mid)+tree[ch[p][1]];
	return query(pos,ch[p][1],mid+1,pr);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>q>>t;
	for(int i=0;i<=n;++i){
		sum[i]=val[i]=1e9;	
	}
	int tmp,fu,fv;
	for(int i=1;i<=m;++i){
		sum[i+n]=val[i+n]=i;
		cin>>secu[i]>>secv[i];
		if(secu[i]==secv[i]){
			root[i]=build(i,1,root[i-1],1,m);
			continue;
		}
		if(find(secu[i])==find(secv[i])){
			split(secu[i],secv[i]);
			tmp=sum[secv[i]];
			cut(tmp+n,secu[tmp]);
			cut(tmp+n,secv[tmp]);
			root[i]=build(tmp,1,root[i-1],1,m);
		}
		else root[i]=root[i-1];
		link(i+n,secu[i]);
		link(i+n,secv[i]);
	}
	int last=0,l,r;
	for(int i=1;i<=q;++i){
		cin>>l>>r;
		if(t>0){
			l=(l+last)%m+1;
			r=(r+last)%m+1;
		}
		if(l>r) swap(l,r);
		cout<<(last=n-r+l-1+query(l,root[r],1,m))<<"\n";
	}
	return 0;
}

:::