Loading...

洛谷P3402 可持久化并查集

check评论:0 条 remove_red_eye浏览量:590 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-20

不会主席树,我就拿离线水过去了

直接树上启发式合并乱搞就好

#include <bits/stdc++.h>
using namespace std;
#define maxn 300010
#define inf 0x3f3f3f3f
int cnt=1,n,m,ty[maxn],a[maxn],b[maxn],tim[maxn],head[maxn],Ans[maxn];
int fa[maxn],siz[maxn];
stack<int> st; 
struct Edge
{ 
    int to,next; 
}e[maxn<<1];
inline void add(int a,int b)
{
    cnt++;
    e[cnt]=(Edge){b,head[a]}; 
    head[a]=cnt;
}
inline void Init()
{
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        siz[i]=1;
    }
}
int find(int x)
{
    return x==fa[x]?x:find(fa[x]);
}
inline void merge(int x, int y)
{
    int fx=find(x),fy=find(y);
    if(fx==fy) 
    {
        return;
    }
    if(siz[fx]<siz[fy]) 
    {
        swap(fx,fy);
    }
    siz[fx]+=siz[fy]; 
    fa[fy]=fx;
    st.push(fy);
}
inline void back()
{
    int y=st.top();
    st.pop();
    siz[fa[y]]-=siz[y]; 
    fa[y]=y;
}
inline void turn(int t=0)
{
    while(st.size()>t) 
    {
        back();
    }
}
void dfs(int x)
{
    tim[x]=st.size();
    if(ty[x]==3) 
    {
        Ans[x]=(find(a[x])==find(b[x]));
    }
    if(ty[x]==1) 
    {
        merge(a[x],b[x]);
    }
    for(int i=head[x];i;i=e[i].next)
    {
        int v=e[i].to;
        dfs(v);
    }  
    turn(tim[x]);
}
int main()
{
    scanf("%d%d", &n, &m);
    Init();
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&ty[i],&a[i]);
        if(ty[i]!=2) 
        {
            scanf("%d",&b[i]);
            add(i-1,i);
        }
        else 
        {
            add(a[i],i);
        }
    }
    dfs(0);
    for(int i=1;i<=m;i++)
    {
        if(ty[i]==3) 
        {
            printf("%d\n",Ans[i]);
        }
    }
    return 0;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名