P13690 [CEOI 2025] boardgames
描述
给定一张无向图，将点按编号划分成若干区间的导出子图，要求满足所有导出子图联通，求最小联通数。
思路
主要来自于 jiangly。
存在比较暴力的做法，依次找到极小的出现断开位置的块，进行递归处理，显然会被做到 \(n^2\)。
对于这类似的划分，可以尝试启发式分裂。
如果我们可以在 \(min(a,b)\) 的时间里，将连通块划分成 \(a\) 和 \(b\) 两个不联通的，进行处理，那确实是可以做到 \(\log\) 的，但是该问题，对于较大的连通块不方便进行删边操作。
可能可以使用LCT进行无脑处理，但是太不优美，这里存在比较优秀的做法。
对于分治的区间 \([l,r]\)，选取中点 \(mid\)，每次只保留 \(mid\) 的所在的区间，这样的分治只包含 \(\log\) 层，因为每次递归下去的长度是 \(\leq \frac{len}{2}\) 的。
但是还是存在删边的问题，我们一般使用可持久化并查集来做带删边的联通性问题，但是在该问题下，他左右两边都要进行撤销操作，我们发现从中间进行加边的时候，左右交错太密集和太稀疏都不是很对。
事实上可以使用二进制分组，我们可以发现这样做单层是 \(log\) 级别的，看上去整体是一个 \(log^2 n\)，但是 jiangly 可以分析到整体 \(n\log n\)，实现也比较快，加上并查集是一个 \(n log^2 n\) 的复杂度，可以通过。
注意到：应当按照边进行分治，每次添加点是 \(O(deg)\) 级别的，而添边是 \(O(1)\) 的，这样才能确保复杂度。
实现：
#include<bits/stdc++.h>
using namespace std;
vector<int> partition_players(int n, int m,vector<int> X,vector<int> Y);
const int maxm=2e5+5;
const int maxn=1e5+5;
struct edge{int x,y,id;
}e[(maxm+maxn)<<1];
set< pair<int,int> > st;
int vc[maxm+maxn];
int fa[maxn],siz[maxn];
int be[maxn],en[maxn];
inline int find(int x){return x==fa[x]?x:find(fa[x]);
}
struct node{int id,val,op;
};
stack<node> st1,st2;
struct seq{int l,r,op;
};
stack<seq> sta;
int tt;
int nl,nr;
inline void add(int l,int r){++tt;sta.push({l,r,tt});for(int i=l;i<=r;i++){st2.push({e[i].id,vc[e[i].id],tt});vc[e[i].id]++;if(vc[e[i].id]==2){int x=find(e[i].x),y=find(e[i].y);if(x!=y){if(siz[x]<siz[y]){st1.push({x,fa[x],tt});fa[x]=y;siz[y]+=siz[x];}else{st1.push({y,fa[y],tt});fa[y]=x;siz[x]+=siz[y];}}}}
}
inline void remove(int o){while(st1.size() && st1.top().op==o){siz[fa[st1.top().id]]-=siz[st1.top().id];fa[st1.top().id]=st1.top().val;st1.pop();}while(st2.size() && st2.top().op==o){vc[st2.top().id]=st2.top().val;st2.pop();}
}
int tw[(maxm+maxn)*2];
inline int get(int b){if(tw[b]) return tw[b];int ret=1;while(ret*2<=b) ret*=2;return tw[b]=ret;
}
inline void add_block(int bl,int br){while(bl || br){if(bl>br){int re=get(bl);add(nl-re,nl-1);nl-=re;bl-=re;}else{int re=get(br);add(nr+1,nr+re);nr+=re;br-=re;}}
}
inline void solve(int l,int r,int bl,int br){if(l==r){st.insert({l,r});return ;}int mid=(l+r)>>1;for(int i=l;i<=r;i++){fa[i]=i,siz[i]=1;}for(int i=bl;i<=br;i++) vc[e[i].id]=0;while(!sta.empty()) sta.pop();while(!st1.empty()) st1.pop();while(!st2.empty()) st2.pop();vector< pair<int,int> > sl;nl=be[mid],nr=en[mid];add(nl,nr);add_block(be[mid]-be[l],en[r]-en[mid]);int L=l,R=r;while(L!=R){bool flag=0;for(int i=1;i<=max(mid-L,R-mid);i++){if(L+i<=mid){if(find(L+i)!=find(L+i-1)){sl.push_back({L,L+i-1});while(1){seq tmp=sta.top();sta.pop();if(tmp.r<be[mid]){nl=tmp.r+1;remove(tmp.op);if(tmp.r+1>=be[L+i]) break;}else{nr=tmp.l-1;remove(tmp.op);}}L+=i;int bl=nl-be[L],br=en[R]-nr;add_block(bl,br);flag=1;break;}}if(R-i>=mid){if(find(R-i)!=find(R-i+1)){sl.push_back({R-i+1,R});while(1){seq tmp=sta.top();sta.pop();if(tmp.r<be[mid]){nl=tmp.r+1;remove(tmp.op);}else{nr=tmp.l-1;remove(tmp.op);if(tmp.l-1<=en[R-i]) break;}}R-=i;int bl=nl-be[L],br=en[R]-nr;add_block(bl,br);flag=1;break;}}}if(!flag) break;}st.insert({L,R});for(auto x:sl){solve(x.first,x.second,be[x.first],en[x.second]);}
}
inline bool cmp(edge x,edge y){if(x.x!=y.x) return x.x<y.x;return x.y<y.y;
}
int tot;
vector<int> partition_players(int n, int m,vector<int> X,vector<int> Y){for(int i=0;i<m;i++){e[++tot]={X[i]+1,Y[i]+1,i+1};e[++tot]={Y[i]+1,X[i]+1,i+1};}for(int i=1;i<=n;i++){int id=tot/2+1;e[++tot]={i,i,id};e[++tot]={i,i,id};}sort(e+1,e+tot+1,cmp);for(int i=1;i<=tot;i++){if(!be[e[i].x]) be[e[i].x]=i;en[e[i].x]=i;}solve(1,n,1,tot);vector<int> ans;for(auto x:st){ans.push_back(x.second-x.first+1);}return ans;
}
/*
int main(){int n,m;scanf("%d%d",&n,&m);vector<int> X,Y;X.resize(m),Y.resize(m);for(int i=0;i<m;i++) scanf("%d%d",&X[i],&Y[i]);vector<int> ans=partition_players(n,m,X,Y);printf("%d\n",(int)ans.size());for(auto x:ans) printf("%d ",x);return 0;
}
*/