做蛋糕招聘网站,芯片最新消息,网站建设管理软件,网络服务丢失CCZ在2015年8月25日也就是初三暑假要结束的时候就已经能切这种题了%%% 学习了另一种启发式合并的方法#xff0c;按秩合并#xff0c;也就是按树的深度合并#xff0c;实际上是和按树的大小一个道理#xff0c;但是感觉#xff08;至少在这题上#xff09;更好处理一些。… CCZ在2015年8月25日也就是初三暑假要结束的时候就已经能切这种题了%%% 学习了另一种启发式合并的方法按秩合并也就是按树的深度合并实际上是和按树的大小一个道理但是感觉至少在这题上更好处理一些。 然后就用可持久化线段树来维护这个可持久化数组就能做到可持久化并查集可持久化平衡树可持久化之类的云云 3673不需要按秩合并3674需要。。。用3674就能过俩双倍经验双倍的幸福 #includeiostream
#includecstdlib
#includecstring
#includecstdio
#includealgorithm
#includequeue
#includecmath
#includemap
#define ll long long
using namespace std;
const int maxn200010,inf1e9;
struct poi{int lt,rt,fa,dep;}tree[maxn*40];
int n,m,ty,x,y,z,tot,sz;
int root[maxn];
void read(int k)
{int f1;k0;char cgetchar();while(c0||c9)c-(f-1),cgetchar();while(c9c0)kk*10c-0,cgetchar();k*f;
}
void build(int x,int l,int r)
{xsz;if(lr){tree[x].fal;return;}int mid(lr)1;build(tree[x].lt,l,mid);build(tree[x].rt,mid1,r);
}
void update(int x,int l,int r,int cx,int delta)
{tree[sz]tree[x];xsz;if(lr){tree[x].fadelta;return;}int mid(lr)1;if(cxmid)update(tree[x].lt,l,mid,cx,delta);else update(tree[x].rt,mid1,r,cx,delta);
}
void add(int x,int l,int r,int cx)
{tree[sz]tree[x];xsz;if(lr){tree[x].dep;return;}int mid(lr)1;if(cxmid)add(tree[x].lt,l,mid,cx);else add(tree[x].rt,mid1,r,cx);
}
int query(int x,int l,int r,int cx)
{if(lr)return x;int mid(lr)1;if(cxmid)return query(tree[x].lt,l,mid,cx);else return query(tree[x].rt,mid1,r,cx);
}
int gf(int k,int x){int xxquery(k,1,n,x);return tree[xx].fax?xx:gf(k,tree[xx].fa);}
int main()
{read(n);read(m);build(root[0],1,n);for(int i1;im;i){read(ty);root[i]root[i-1];if(ty1){read(x);read(y);xgf(root[i],x);ygf(root[i],y);if(tree[x].fatree[y].fa)continue;if(tree[x].deptree[y].dep)swap(x,y);update(root[i],1,n,tree[x].fa,tree[y].fa);if(tree[x].deptree[y].dep)add(root[i],1,n,tree[y].fa);}else if(ty2)read(x),root[i]root[x];else read(x),read(y),printf(%d\n,tree[gf(root[i],x)].fatree[gf(root[i],y)].fa);}return 0;
} View Code转载于:https://www.cnblogs.com/Sakits/p/7418281.html
