二进制拆分做法，感觉十分巧妙。

首先有个贪心，对于一个区间 $[l,r]$，每次找到一个点 $p$，满足 $p$ 和 $p+1$ 不连通，然后将 $[l,r]$ 断开。断到不能断为止。

先引出一个众所周知的结论，设一个区间分裂后，两个区间中长度较小的是 $mn$，那么 $\sum mn=n\log n$。

那么对于区间 $[l,r]$，我们从两边往中间扫，去找一个 $p$，然后考虑分开，继续这样做，可以发现这样的总量是 $O(n\log n)$ 的。

设 $sol(l,r)$ 表示处理 $[l,r]$，那么假设 $[l,r]$ 被分为了 $[l,p],[p+1,r]$ 两个部分，那么可以递归处理（也就是暴力重构）长度较小的部分，然后删去一段前缀或后缀，继续处理长度较大的一部分。

问题在于如何快速删去一段前缀或后缀。

考虑关心其加边顺序，然后用可撤销并查集来维护这个操作。

设 $mid=\frac{l+r}{2}$。

一个十分巧妙的思路是考虑二进制分组，分别将 $[l,mid],[mid+1,r]$ 这两个区间分为 $\log n$ 组，然后按长度降序排序，依次加入并查集，一个区间 $[l,r]$ 要变成 $[L,R]$，那么直接撤销到 $[L,R]\subseteq [l,r]$ 为止。剩下还没填的暴力加进去就行了，然后还是按上述方式加，容易发现还要再加入的点的数量是“删去的长度”级别的。

这样我们只会进行 $O(m\log n)$ 次加入或撤销并查集，所以时间复杂度是 $O(m\log^2 n)$。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int Maxn=2e5+5;
int n,m;
struct edge{
	int u,v;
}e[Maxn];
vector<int>G[Maxn];

struct NODE{
	int l,r;
	inline bool operator<(const NODE&b)const{
		return r<b.r;
	}
};
vector<NODE>ans;


int fa[Maxn],si[Maxn];
inline int find(int x){
	while(fa[x]^x)x=fa[x];
	return x;
}
stack<int>stk;
inline void merge(int u,int v){
	u=find(u);v=find(v);
	if(u==v)return;
	if(si[u]<si[v])swap(u,v);
	stk.push(v);
	fa[v]=u;si[u]+=si[v];
}
struct node{
	int l,r,len;
};
int vis[Maxn];
inline void del(node it){
	for(int i=it.l;i<=it.r;i++)vis[i]=0;
	int len=it.len;
	while(stk.size()>len){
		int u=stk.top();stk.pop();
		si[fa[u]]-=si[u];
		fa[u]=u;
	}
}
void solve(int l,int r){
	if(l>r)return;
	if(l==r){
		ans.push_back({l,r});
		return;
	}
	int mid=l+r>>1;
	for(int i=l;i<=r;i++)fa[i]=i,si[i]=1;
	while(!stk.empty())stk.pop();
	vector<node>a;
	int now=mid+1;
	for(int i=18;~i;i--)if(now+(1<<i)-1<=r){
		a.push_back({now,now+(1<<i)-1,0});
		now+=(1<<i);
	}
	
	now=mid;
	for(int i=18;~i;i--)if(now-(1<<i)+1>=l){
		a.push_back({now-(1<<i)+1,now,0});
		now-=(1<<i);
	}
	
	sort(a.begin(),a.end(),[&](node a,node b){return a.r-a.l>b.r-b.l;});
	for(int i=0;i<a.size();i++){
		a[i].len=stk.size();
		for(int u=a[i].l;u<=a[i].r;u++)vis[u]=1;
		for(int u=a[i].l;u<=a[i].r;u++)
			for(int v:G[u])if(vis[v])merge(u,v);
	}
	
	
//	printf("now:[%d,%d]\n",l,r);
//	for(int i=l;i<=r;i++)printf("fa[%d]=%d   ",i,fa[i]);
//	puts("");
	
	vector<node>tpp;
	
	while(1){
		int p=-1;
		for(int len=1;len<r-l+1;len++){
			int L=l+len,R=r-len;
			if(find(L-1)!=find(L)){
				p=L-1;break;
			}
			if(find(R)!=find(R+1)){
				p=R;break;
			}
		}
//		for(int i=l;i<=r;i++)printf("fa[%d]=%d   ",i,fa[i]);
//		puts("");
//		printf("jhoigfhogfhntroi [%d,%d,%d]\n",l,r,p);
		if(p==-1){
			ans.push_back({l,r});
			break;
		}
		int L,R;
		if(p-l+1<=r-p){
			L=p+1;R=r;tpp.push_back({l,p,0});
		}else{
			L=l;R=p;tpp.push_back({p+1,r,0});
		}
		while((l<L||R<r)&&l<=r){
			node it=a.back();a.pop_back();
			del(it);
//			printf("L=%d,R=%d    (%d,%d)     it:(%d,%d)\n",L,R,l,r,it.l,it.r);
			if(l==it.l)l=it.r+1;
			if(r==it.r)r=it.l-1;
		}assert(L<=R);
		if(l>r){
			int Mid=L+R>>1;
			l=Mid;r=Mid-1;
		}
		vector<node>b;
		r++;
		for(int i=18;~i;i--)if(r+(1<<i)-1<=R){
			b.push_back({r,r+(1<<i)-1,0});
			r+=(1<<i);
		}r--;
		
		l--;
		for(int i=18;~i;i--)if(l-(1<<i)+1>=L){
			b.push_back({l-(1<<i)+1,l,0});
			l-=(1<<i);
		}l++;
		sort(b.begin(),b.end(),[&](node a,node b){return a.r-a.l>b.r-b.l;});
		for(int i=0;i<b.size();i++){
			b[i].len=stk.size();
			for(int u=b[i].l;u<=b[i].r;u++)vis[u]=1;
			for(int u=b[i].l;u<=b[i].r;u++)
				for(int v:G[u])if(vis[v])merge(u,v);
			a.push_back(b[i]);
		}
//		printf("a:");
//		for(node it:a)printf("%d ",it.r-it.l+1);puts("");
	}
//	puts("do this!");
	for(int i=l;i<=r;i++)vis[i]=0;
	for(node it:tpp)solve(it.l,it.r);
}
vector<int> partition_players(int N,int M,vector<int>X,vector<int>Y){
	n=N;m=M;
	for(int i=1;i<=m;i++){
		e[i]={X[i-1]+1,Y[i-1]+1};
		G[e[i].u].push_back(e[i].v);
		G[e[i].v].push_back(e[i].u);
//		printf("e(%d,%d)\n",e[i].u,e[i].v);
	}
	solve(1,n);
	sort(ans.begin(),ans.end());
	vector<int>res;
	for(NODE p:ans)res.push_back(p.r-p.l+1);
	return res;
}