自动搬运

查看原文

来自洛谷，原作者为

	Gao_yc 谁需要这不解风情又潦草的总结

搬运于2025-08-24 22:47:20，当前版本为作者最后更新于2023-05-21 09:40:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目实际上是要求图的连通块情况。

不妨设 $fa_i$ 为 与 $i$ 联通的点的最小编号，那么题目就能转化为求 $fa_i$。

于是有两种情况：

1.$fa_i=i$，即 $i$ 与 $1 \sim i-1$ 的点均不连通，是一个新加入的连通块。

2.$fa_i < i$。

先考虑如何判断第一种情况。

设 $rt_i$ 表示满足前 $i$ 个点联通的礼物编号，那么只要满足 $rt_{i-1} \ne rt_i = Connected(rt_{i-1},i-1,i)$ 即可。

而对于第二种情况，可以二分查找 $fa_i$，通过查询 $Connected(rt_{mid},mid,i)$ 是否为 $rt_{mid}$ 来判断。

设连通块个数为$s$，则询问次数为 $\mathcal{O}((n-s) \log n)$。

但是这样可以被特定的数据卡掉。

优化：

显然，如果 $Connected(rt_x,x,i)=rt_x$，那么 $Connected(rt_{fa_x},fa_x,i)=rt_{fa_x}$，而 $fa_x \le x$。

因此如果 $x$ 满足条件，$fa_x$ 必定也满足条件。

于是我们只要二分 $fa_i=i$ 的点就好了。

询问次数 $\mathcal{O}((n-s) \log s)$。

优化效果：构造 $n=m=200$ 的数据，不加优化询问次数 $1390$。

优化之后询问次数 $570$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=210;
int rt[N],fa[N],cnt,las;
int a[N],top;
vector<pair<int,int> > ans;
int Connected(int a, int i, int j);
void DescribeDesign(std::vector<std::pair<int, int>> result);
void ToyDesign(int n,int max_ops){
	fa[1]=1;rt[1]=0;a[top=1]=1;
	for(int i=2;i<=n;++i){
		rt[i]=Connected(rt[i-1],i-1,i);cnt++;
		if(rt[i]!=rt[i-1]){
			fa[i]=i;
			a[++top]=i;
			continue;
		}
		int l=1,r=top,res=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(a[mid]==i-1) {r=mid-1;continue;} 
			cnt++;
			if(Connected(rt[a[mid]],a[mid],i)==rt[a[mid]]) r=mid-1;
			else l=mid+1,res=mid;
		}
		fa[i]=a[res+1];
	}
	for(int i=1;i<=n;++i) if(fa[i]!=i) ans.push_back(make_pair(fa[i],i));
	DescribeDesign(ans);
	return;
}