CF1706E 题解

你谷题目传送门

CF 题目传送门

题目大意

给定一个 \(n\) 个点 \(m\) 条边的无向图，询问 \(q\) 次，每次询问会指定两个正整数 \(l,r\)，问要使对于 \(l \leq a \leq b \leq r\) 的所有 \(a,b\) 均有路径可以互相到达，最少需要加入前多少条边。

思路

考虑到每一次询问实质上就是问你在按顺序加了多少条边之后，编号 \([l,r]\) 之间的点都在同一个联通块中。

记 \(mintim(i)\) 表示 \(i\) 和 \(i+1\) 在加了 \(mintim(i)\) 条边之后处在同一个联通块，那么每一次询问的答案就是 \(\max_{i=l}^{r-1} mintim(i)\)。

在求解出所有的 \(mintim(i)\) 之后就可以直接用 ST 表或者线段树解决区间查询。

那么现在问题在于怎么求解 \(mintim(i)\)。

考虑顺序加边用启发式合并的思想处理 \(mintim(i)\)，具体操作流程如下：

• 当前要合并 \(x,y\) 所在的集合 \(S(x),S(y)\)。
• 如果 \(|S(x)|<|S(y)|\)，那么遍历 \(S(x)\) 中的每一个元素 \(p \in S(x)\)，处理 \(mintim(p-1)\) 和 \(mintim(p)\)。
• 否则交换 \(x,y\) 再操作即可。

不难看出每一个点在启发式合并的过程中最多被合并 \(\log_2 n\) 次，而并查集复杂度为 \(O(α(n))\)，所以处理 \(mintim\) 的这一部分复杂度为 \(O(n \log_2 n α(n))\)。

总时间复杂度 \(O(n \log_2 n α(n)+q \log_2 n)\)，可以通过本题。

#include<bits/stdc++.h>

#define RI register int
#define ll long long
#define ull unsigned long long
#define YES puts("YES")
#define NO puts("NO")

using namespace std;

namespace IO{
	inline int read(){
		RI X=0, W=0;register char ch=getchar();
		while(!isdigit(ch)) W|=ch=='-', ch=getchar();
		while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
		return W?-X:X;
	}
	inline void write(int x){
		if(x<0) x=-x, putchar('-');
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
}using namespace IO;

const int MAXN = 2e5+5;

int n, m, q;
int fa[MAXN];
int tree[MAXN << 2], minn[MAXN];
int siz[MAXN];

vector<int> G[MAXN];

inline int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}

inline void build(int p, int l, int r){
	if(l==r){
		tree[p]=minn[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid), build(p<<1|1,mid+1,r);
	tree[p]=max(tree[p<<1],tree[p<<1|1]);
}

inline int ask(int p, int l, int r, int L, int R){
	if(L>R) return 0;
	if(L<=l && r<=R) return tree[p];
	int mid=(l+r)>>1, res=0;
	if(L<=mid) res=ask(p<<1,l,mid,L,R);
	if(R>mid) res=max(res,ask(p<<1|1,mid+1,r,L,R));
	return res;
}

inline void solve(){
	//4 [space]
	n=read(),m=read(),q=read();int p;fa[n+1]=n+1;
	for(int i=1;i<=n;++i) G[i].clear(), G[i].push_back(i), fa[i]=i, siz[i]=1, minn[i]=1e9;
	for(int i=1;i<=m;++i) {
		int x, y;
		x=read(), y=read();
		x=find(x), y=find(y);
		if(x==y) continue;
		if(siz[x]>siz[y]) swap(x,y);
		siz[y]+=siz[x];fa[x]=y;
		for(int A=0;A<G[x].size();++A){
			p=G[x][A];
			if(find(p)==find(p+1)) minn[p]=min(i,minn[p]);
			if(find(p)==find(p-1)) minn[p-1]=min(minn[p-1],i);
			G[y].push_back(p);
		}
		G[x].clear();siz[x]=0;
	}
	build(1,1,n-1);
	while(q--){
		int l, r;
		l=read(), r=read();
		write(ask(1,1,n-1,l,r-1)), putchar(32);
	}
	putchar(10);
}

int main(){
	int t=read();
	while(t--) solve();
	return 0;
}

最后附上 评测记录。