湖州做网站建设的公司,网站设计说明范文,wap商城网站模板素材,网站开发专业怎么样蒟蒻比较菜#xff0c;现在才学。。。 P3402 可持久化并查集 其实就是魔改的主席树啦#xff0c;记录每个点的直接父亲与这棵子树的大小。 合并的时候不用路径压缩#xff0c;直接暴力跳父亲#xff0c;\(O(\log^2)\) 找到祖先#xff0c;之后启发式合并(启发式合并的平均… 蒟蒻比较菜现在才学。。。 P3402 可持久化并查集 其实就是魔改的主席树啦记录每个点的直接父亲与这棵子树的大小。 合并的时候不用路径压缩直接暴力跳父亲\(O(\log^2)\) 找到祖先之后启发式合并(启发式合并的平均复杂度达到 \(O(\log n)\))。 需要注意的是可能会先继承删一个版本并有两次在同一个版本上的修改。这是我们需要先复制版本再在这个版本上动态开点修改父亲。 $\texttt{code}$ // Author:A weak man named EricQian
#includebits/stdc.h
using namespace std;
#define infll 0x7f7f7f7f7f7f7f7f
#define inf 0x3f3f3f3f
#define Maxn 200005
typedef long long ll;
inline int rd()
{int x0;char ch,t0;while(!isdigit(ch getchar())) t|ch-;while(isdigit(ch)) xx*10(ch^48),chgetchar();return xt?-x:x;
}
inline ll maxll(ll x,ll y){ return xy?x:y; }
inline ll minll(ll x,ll y){ return xy?x:y; }
inline ll absll(ll x){ return x0ll?x:-x; }
inline ll gcd(ll x,ll y){ return (y0)?x:gcd(y,x%y); }
int n,m,tot;
int root[Maxn];
struct TREE { int ls,rs,fa,siz; }tree[Maxn5];
void build(int p,int nl,int nr)
{if(!p) ptot;if(nlnr){ tree[p].fanl,tree[p].siz1; return; }int mid(nlnr)1;build(tree[p].ls,nl,mid),build(tree[p].rs,mid1,nr);
}
TREE query(int p,int nl,int nr,int x)
{if(nlnr) return tree[p];int mid(nlnr)1;if(midx) return query(tree[p].ls,nl,mid,x);else return query(tree[p].rs,mid1,nr,x);
}
TREE Find(int p,int x)
{TREE tmpquery(p,1,n,x);if(tmp.fax) return tmp;return Find(p,tmp.fa);
}
void change(int p,int nl,int nr,int x,int F,int S)
{if(nlnr) { tree[p].faF,tree[p].sizS; return; }int mid(nlnr)1;if(midx){tree[tot]tree[tree[p].ls],tree[p].lstot;change(tree[p].ls,nl,mid,x,F,S);}else{tree[tot]tree[tree[p].rs],tree[p].rstot;change(tree[p].rs,mid1,nr,x,F,S);}
}
int main()
{//ios::sync_with_stdio(false); cin.tie(0);//freopen(.in,r,stdin);//freopen(.out,w,stdout);nrd(),mrd(),build(root[0],1,n);TREE sa,sb;for(int i1,opt,a,b,k;im;i){optrd();if(opt1){root[i]tot,tree[root[i]]tree[root[i-1]];ard(),brd(),saFind(root[i],a),sbFind(root[i],b);
// if(sa.fasb.fa) continue;if(sa.sizsb.siz)change(root[i],1,n,sb.fa,sa.fa,sb.siz),change(root[i],1,n,sa.fa,sa.fa,sa.sizsb.siz);elsechange(root[i],1,n,sa.fa,sb.fa,sa.siz),change(root[i],1,n,sb.fa,sb.fa,sa.sizsb.siz);}else if(opt2) krd(),root[i]root[k];else{ard(),brd(),root[i]root[i-1];saFind(root[i],a),sbFind(root[i],b);if(sa.fasb.fa) printf(1\n);else printf(0\n);}}//fclose(stdin);//fclose(stdout);return 0;
}
