自动搬运

查看原文

来自洛谷，原作者为

	forest114514 AFO|成也集合幂级数，败也集合幂级数|O Fortuna, velut luna,statu variabilis.

搬运于2025-08-24 22:49:58，当前版本为作者最后更新于2024-07-15 16:32:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P9598 [JOI Open 2018] 山体滑坡

给一个认为 $\alpha(n)$ 近似于 $O(1)$ 和 $n,q,c$ 同阶时时间复杂度为 $O(n\sqrt n)$ 的做法。

一句话，多次删边和加边，问你 $[0,x]$ 和 $[x+1,n-1]$ 两个点集和其点集间的连边构成的联通块数之和，然后不难发现两部分是独立的，以 $[0,x]$ 为例。

没有修改考虑按 $x$ 排序用并查集加点维护联通块数量，可以做到线性对数；有修改时发现修改对询问的贡献需要花费 $\Theta(\text{修改数量})$ 的时间，自然想到操作分块，吐槽一下删除操作就是纯纯增加代码量但没有任何思维含量的东西。

我们 $B$ 个操作分一块，块内询问按 $x$ 排序，然后每次询问相当于在原图基础上加 $O(B)$ 条边再问你连通块的数量。

新加边还要撤回操作的话使用可撤销并查集多一个 $\log n$ 的复杂度，此时时间为 $O(qB\log n+\frac{nc}{B}\log n)=O(n\sqrt n\log n)$ ，注意到除了询问的时候加边之外不需要撤销直接路径压缩，可以做到 $O(qB\log n+\frac{nc}{B})=O(n\sqrt {n\log n})$。

不过都不是很牛，我们想一想怎么优化？

我们考虑在 $[0,x]$ 点集加上 $B$ 条边后的连通块数就是 $[0,x]$ 形成的连通块数减去 $B$ 条边合并的联通块数，考虑把 $[0,x]$ 的联通块按其 $fa$ 缩成一个点，然后再这个 $O(B)$ 个点的新图上看减少了几个连通块，可以用一个新的并查集来维护，然后就能 $O(B)$ 完成单组询问，最后做到 $O(qB+\frac{nc}{B})=O(n\sqrt n)$ 的时间复杂度，当然空间复杂度是 $O(n)$。

代码：

const int N=1e5+100,B=350;
int n,c,q,x[N],y[N],e[N],op[N],ans[N],fa[N],ff[N],tot,cnt,cnt2,ct;
LL hs[N];
int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);} 
int getf2(int x){return x==ff[x]?x:ff[x]=getf2(ff[x]);}
vector<pii> que[N],opt[N];
vector<int> E[N];
bool vis[N],fl[N];
void merge(int x,int y){
	x=getf(x),y=getf(y);
	if(x==y) return;
	++cnt,fa[x]=y;
}
void add(int x,int y){
	x=getf(x),y=getf(y);
	if(x==y) return;
	x=getf2(x),y=getf2(y);
	if(x==y) return;
	ff[x]=y,++cnt2;
}
void del(int x,int y){
	x=getf(x),y=getf(y);
	ff[x]=x,ff[y]=y;
}
//bool _ED;
signed main(){
	//fprintf(stderr,"%.20lf MB\n",(&_ST-&_ED)/1048576.0);
	//ios::sync_with_stdio(false);
	//cin.tie(0);cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	read(n,c,q);
	rep(i,1,c) {
		read(op[i],x[i],y[i]);
		++x[i],++y[i];
		if(x[i]>y[i]) swap(x[i],y[i]);
		hs[i]=1ll*x[i]*n+y[i];
	}
	sort(hs+1,hs+1+c);
	ct=unique(hs+1,hs+1+c)-hs-1;
	rep(i,1,c) e[i]=lower_bound(hs+1,hs+1+ct,1ll*x[i]*n+y[i])-hs;
	rep(i,1,q){
		int t,x;
		read(t,x);
		++t,++x;
		que[t].pb({x,i});
	}
	tot=(c+B-1)/B;
	int l=0,r=0;
	
	rep(T,1,tot){
		l=r+1,r=min(l+B-1,c);
		rep(i,l,r) fl[e[i]]=1;
		
		rep(i,1,n) opt[i].clear(),ff[i]=fa[i]=i,E[i].clear();
		rep(i,l,r) for(auto j:que[i]) opt[j.fi].pb({i,j.sc});
		rep(i,1,l-1) if(vis[e[i]]&&(!fl[e[i]])) E[y[i]].pb(x[i]);
		cnt=0;
		rep(u,1,n){
			for(auto v:E[u]) merge(u,v);
			for(auto j:opt[u]){
				int t=j.fi,id=j.sc;
				cnt2=0;
				rep(i,l,t) vis[e[i]]^=1;
				rep(i,l,r) if(vis[e[i]]&&y[i]<=u) add(x[i],y[i]);
				ans[id]-=cnt+cnt2;
				rep(i,l,r) del(x[i],y[i]);
				rep(i,l,t) vis[e[i]]^=1;
			}
		}
		
		rep(i,1,n) opt[i].clear(),ff[i]=fa[i]=i,E[i].clear();
		rep(i,l,r) for(auto j:que[i]) opt[j.fi+1].pb({i,j.sc});
		rep(i,1,l-1) if(vis[e[i]]&&(!fl[e[i]])) E[x[i]].pb(y[i]);
		cnt=0;
		per(u,n,1){
			for(auto v:E[u]) merge(u,v);
			for(auto j:opt[u]){
				int t=j.fi,id=j.sc;
				cnt2=0;
				rep(i,l,t) vis[e[i]]^=1;
				rep(i,l,r) if(vis[e[i]]&&x[i]>=u) add(x[i],y[i]);
				ans[id]-=cnt+cnt2;
				rep(i,l,r) del(x[i],y[i]);
				rep(i,l,t) vis[e[i]]^=1;
			}
		}
		rep(i,l,r) vis[e[i]]^=1,fl[e[i]]=0;
	}
	rep(i,1,q) write(n+ans[i],'\n');
	//fprintf(stderr,"%.4lf s\n",1.0*clock()/CLOCKS_PER_SEC);
	return 0;
}