Loading...

洛谷P3835 [模板]可持久化平衡树

check评论:0 条 remove_red_eye浏览量:348 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-04-04

蒟蒻表示不会fhq...

那就来$01trie$吧qwq

和主席树的思想一样,记录一个$siz$,然后尽量使用以前的数据即可,然后其他就是普通平衡树了

/**************************/
/*It is made by decoration*/
/**************************/
#include <bits/stdc++.h>
using namespace std;
#define maxn 500010
#define int long long
const int inf=1e9;
int rt[maxn],ch[maxn<<5][2],siz[maxn],cnt;
void ins(int &now,int pre,int x)
{
    now=++cnt,x+=inf;
    int qaq=now;
    siz[now]=siz[pre]+1;
    for(int i=31;i>=0;i--)
    {
        int qwq=(x>>i)&1;
        ch[qaq][qwq]=++cnt;
        ch[qaq][qwq^1]=ch[pre][qwq^1];
        qaq=ch[qaq][qwq],pre=ch[pre][qwq];
        siz[qaq]=siz[pre]+1;
    }
}
void del(int &now,int pre,int x)
{
    x+=inf;
    int pt=pre;
    for(int i=31;i>=0;i--)
    {
        int qwq=(x>>i)&1;
        pt=ch[pt][qwq];
        if(!siz[pt])
        {
            now=pre;
            return ;
        }
    }
    now=++cnt;
    int qaq=now;
    siz[now]=siz[pre]-1;
    for(int i=31;i>=0;i--)
    {
        int qwq=(x>>i)&1;
        ch[qaq][qwq]=++cnt;
        ch[qaq][qwq^1]=ch[pre][qwq^1];
        qaq=ch[qaq][qwq],pre=ch[pre][qwq];
        siz[qaq]=siz[pre]-1;
    }
}
int rnk(int pre,int x)
{
    x+=inf;
    int now=0;
    for(int i=31;i>=0;i--)
    {
        int qaq=(x>>i)&1;
        if(qaq)
        {
            now+=siz[ch[pre][0]],pre=ch[pre][1];
        }
        else
        {
            pre=ch[pre][0];
        }
    }
    return now;
}
int kth(int pre,int x)
{
    int now=0;
    for(int i=31;i>=0;i--)
    {
        if(x>siz[ch[pre][0]])
        {
            now|=(1<<i),x-=siz[ch[pre][0]];
            pre=ch[pre][1];
        }
        else
        {
            pre=ch[pre][0];
        }
    }
    return now-inf;
}
main()
{
    ins(rt[0],rt[0],inf),ins(rt[0],rt[0],-inf);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int v,opt,x;
        scanf("%lld%lld%lld",&v,&opt,&x);
        if(opt==1)
        {
            ins(rt[i],rt[v],x);
        }
        if(opt==2)
        {
            del(rt[i],rt[v],x);
        }
        if(opt==3)
        {
            rt[i]=rt[v];
            printf("%lld\n",rnk(rt[i],x));
        }
        if(opt==4)
        {
            rt[i]=rt[v];
            printf("%lld\n",kth(rt[i],x+1));
        }
        if(opt==5)
        {
            rt[i]=rt[v];
            int qaq=kth(rt[i],rnk(rt[i],x));
            if(qaq==-inf)
            {
                printf("-2147483647\n");
            }
            else
            {
                printf("%lld\n",qaq);
            }
        }
        if(opt==6)
        {
            rt[i]=rt[v];
            int qaq=kth(rt[i],rnk(rt[i],x+1)+1);
            if(qaq==inf)
            {
                printf("2147483647\n");
            }
            else
            {
                printf("%lld\n",qaq);
            }
        }
    }
    
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名