视频链接:
P4219 [BJOI2014] 大融合 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <map> using namespace std; #define ls (u<<1) #define rs (u<<1|1) #define mid ((l+r)>>1) const int N=100005; int n,m; int p[N],siz[N],top; //并查集 vector<pair<int,int>> tr[N<<4]; //节点 struct node{ int x,y; }st[N<<1]; //栈 void insert(int u,int l,int r,int L,int R,pair<int,int> e){ if(L<=l&&r<=R) return tr[u].push_back(e); if(L<=mid) insert(ls,l,mid,L,R,e); if(R>mid) insert(rs,mid+1,r,L,R,e); } int find(int x){ //查找根 return p[x]==x?x:find(p[x]); } void merge(int x,int y){ //合并集合 x=find(x),y=find(y); if(x==y) return; if(siz[x]>siz[y]) swap(x,y); st[++top]={x,y}; p[x]=y; siz[y]+=siz[x]; } int cnt,tim,ans[N<<2]; struct tims{ pair<int,int> e; int l,r; }tms[N<<2]; //边出现的时间 map<pair<int,int>,int> et; //边出现的时刻 map<int,pair<int,int>> qe; //该时刻查询的边 map<int,bool> qt; //查询时刻的标记 void solve(int u,int l,int r){ int now=top; for(auto i:tr[u]) merge(i.first,i.second); if(l==r){ if(qt[l]){ int x=qe[l].first,y=qe[l].second; ans[l]=siz[find(x)]*siz[find(y)]; } } else solve(ls,l,mid),solve(rs,mid+1,r); while(top>now){ //撤销合并 node s=st[top--]; p[s.x]=s.x; siz[s.y]-=siz[s.x]; } } int main(){ scanf("%d%d",&n,&m); char c[5]; int x,y; for(int i=1;i<=n;i++) p[i]=i,siz[i]=1; while(m--){ scanf("%s%d%d",c,&x,&y); if(x>y) swap(x,y); //保证边的映射 pair<int,int> e={x,y}; if(c[0]=='A') et[e]=++tim; //e出现的时刻 else{ tms[++cnt]={e,et[e],tim}; //e出现的时间 qe[++tim]=e; //tim时刻查询的边 qt[tim]=1; //查询时刻的标记 et[e]=++tim; //e再次出现时刻 } } for(auto i:et) //每条边出现的时间 tms[++cnt]={i.first,et[i.first],tim}; for(int i=1;i<=cnt;i++) insert(1,1,tim,tms[i].l,tms[i].r,tms[i].e); solve(1,1,tim); for(int i=1;i<=tim;i++) if(qt[i])printf("%d\n",ans[i]); }
标签:C136,int,siz,++,BJOI2014,find,tim,et,P4219 From: https://www.cnblogs.com/dx123/p/18239905