求助,并查集维护splay平衡树卡住了,不知道为什么

回复帖子

@ViXpop 2019-01-30 11:51 回复
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=10000005;
const int M=100005;

int n,m,ak,to[N],cnt,nxt[N],head[N],a[N],num[N],flag[N],child[M][2],fa[N],ct[N],root,id,q[N];
int _search(int x,int w)
{
    while(a[x]!=w)
    {
        if(a[x]>w)
        {
            if(child[x][0])x=child[x][0];
            else return x;
        }
        else if(a[x]<w)
        {
            if(child[x][1])x=child[x][1];
            else return x;
        }
    }
    return x;
}
void _rotate(int x)
{
    int y=fa[x];
    int z=fa[y];
    if(child[z][0]==y)child[z][0]=x;else child[z][1]=x;
    fa[x]=z;
    int w;
    if(child[y][0]==x)w=0;else w=1;
    child[y][w]=child[x][w^1];
    fa[child[x][w^1]]=y;
    child[x][w^1]=y;
    fa[y]=x;
    ct[y]=ct[child[y][0]]+ct[child[y][1]]+num[y];
    ct[x]=ct[child[x][0]]+ct[child[x][1]]+num[x];
}
void splay(int x)
{
    while(fa[x])
    {
        int y=fa[x];
        int z=fa[y];
        if(z==0)_rotate(x);
        else
        {
            if((child[z][0]==y)^(child[y][0]==x))
                _rotate(x);
            else
                _rotate(y);
            _rotate(x);
        }
    }
    root=x;
}
void _insert(int x)
{
    if(id==0)
    {
        id=1;fa[1]=0;root=1;num[1]=1;a[1]=x;child[1][0]=0;child[1][1]=0;ct[1]=1;
    }
    else
    {
        int node=0;
        int k=_search(root,x);
        if(a[k]==x)
        {
            num[k]++;
            node=k;
        }
        else
        {
            ++id;
            a[id]=x;fa[id]=k;if(x<a[k])child[k][0]=id;else child[k][1]=id;
            num[id]=1;ct[id]=1;
        }
        while(k)
        {
            ct[k]++;
            k=fa[k];
        }
        if(node)splay(node);else splay(id);
    }
}
int _find(int x)
{
    int k=root;
    while(x<ct[child[k][0]]+1||x>ct[child[k][0]]+num[k])
    {
        if(x<ct[child[k][0]]+1)k=child[k][0];
        else {x-=(ct[child[k][0]]+num[k]);k=child[k][1];}
    }
    return a[k];
}
void _del(int x)
{
    int k=_search(root,x);
    if(a[k]==x)
    {
        splay(k);
        if(num[k]>1)num[k]--,ct[k]--;
        else
        {
            if(child[k][0]==0)
            {
                root=child[k][1];
                child[k][1]=0;
                fa[root]=0;
            }
            else if(child[k][1]==0)
            {
                root=child[k][0];
                fa[root]=0;
            }
            else
            {
                int kk=_search(child[k][0],2147483647);
                splay(kk);
                fa[child[k][1]]=kk;
                child[kk][1]=child[k][1];
                ct[root]--;
            }
        }
    }
}
void init()
{
    for(register int i=1;i<=n;i++)
        fa[i]=i;
}
int findf(int x)
{
    if(fa[x]==x)
        return x;
    else
        fa[x]=findf(fa[x]);
    return fa[x];
}
int hb(int x,int y)
{
    int fx=findf(x);
    int fy=findf(y);
    fa[fx]=fy;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;i++)
        scanf("%d",&q[i]);
    init();
    for(register int i=1;i<=m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        hb(l,r);
    }
    scanf("%d",&ak);
    for(register int i=1;i<=ak;i++)
    {
        int l,r;char s;
        scanf("%c%d%d",&s,&l,&r);
        if(s=='Q')
        {
            for(register int i=1;i<=n;i++)
            {
                if(findf(i)==findf(l)&&i!=l)
                {
                    _insert(i);
                    flag[i]=1;
                }
            }
            if(!_find(r))printf("-1\n");
            else printf("%d\n",_find(r));
            for(register int i=1;i<=n;i++)
            {
                if(flag[i])_del(i);flag[i]=0;
            }
        }
        else
            hb(l,r);
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。