P3835 【模板】可持久化平衡树 题解

以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • 还没有评论
作者: 大奕哥 更新时间: 2017-12-04 15:44  在Ta的博客查看    3  

fhq Treap可持久化,使用split(分裂),merge(合并)两个操作

对于删除操作:我们将小于等于他最大的点找出来,我们再将排除小于他的点后最小的点找出来,然后将这两个点合并在一起。

对于插入操作:我们将小于等于他的点找出来进行合并即可。

时间复杂度O(qlogq),空间复杂度(qlogq)。

推广Blog:http://www.cnblogs.com/nbwzyzngyl/p/7977369.html

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int l,r;int size,rnd,v;
}t[500005*50];
int cnt,rt[500005];
void update(int k)
{
    t[k].size=t[t[k].l].size+t[t[k].r].size+1;
}
void newnode(int &k,int x)
{
    t[k=++cnt].v=x;t[k].size=1;t[k].rnd=rand();
}
int merge(int a,int b)
{
    if(!a||!b)return a+b;
    if(t[a].rnd>t[b].rnd)
    {
        int p=++cnt;t[p]=t[a];
        t[p].r=merge(t[p].r,b);
        update(p);return p;
    }
    else
    {
        int p=++cnt;t[p]=t[b];
        t[p].l=merge(a,t[p].l);
        update(p);return p;
    }
}
void split(int now,int k,int &x,int &y)
{
    if(!now)x=y=0;
    else
    {
        if(t[now].v<=k)
        {
            x=++cnt;t[x]=t[now];
            split(t[x].r,k,t[x].r,y);
            update(x);
        }
        else 
        {
            y=++cnt;t[y]=t[now];
            split(t[y].l,k,x,t[y].l);
            update(y);
        }
    }
}
void Delete(int &root,int w)
{
    int x=0,y=0,z=0;
    split(root,w,x,z);
    split(x,w-1,x,y);
    y=merge(t[y].l,t[y].r);
    root=merge(merge(x,y),z);
}
void Insert(int &root,int w)
{
    int x=0,y=0,z=0;
    split(root,w,x,y);
    newnode(z,w);
    root=merge(merge(x,z),y);
}
int getval(int k,int w)
{
    if(w==t[t[k].l].size+1)return t[k].v;
    else if(w<=t[t[k].l].size)return getval(t[k].l,w);
    else return getval(t[k].r,w-t[t[k].l].size-1);
}
int getkth(int &root,int w)
{
    int x,y;
    split(root,w-1,x,y);
    int ans=t[x].size+1;
    root=merge(x,y);
    return ans;
}
int getpre(int &root,int w)
{
    int x,y,k,ans;
    split(root,w-1,x,y);
    if(!x)return -2147483647;
    k=t[x].size;
    ans=getval(x,k);
    root=merge(x,y);
    return ans;
}
int getnex(int &root,int w)
{
    int x,y,ans;
    split(root,w,x,y);
    if(!y)return 2147483647;
    else ans=getval(y,1);
    root=merge(x,y);
    return ans;
}
int main()
{
    int n,f,w,tim;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d%d",&tim,&f,&w);
        rt[i]=rt[tim];
        if(f==1)Insert(rt[i],w);
        else if(f==2)Delete(rt[i],w);
        else if(f==3)printf("%d\n",getkth(rt[i],w));
        else if(f==4)printf("%d\n",getval(rt[i],w));
        else if(f==5)printf("%d\n",getpre(rt[i],w));
        else printf("%d\n",getnex(rt[i],w));
    }
    return 0;
}