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


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

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

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

评论

  • SovietPower✨
    一点(很小的)优化? 操作3.4.5.6都不会改原树,root[i]=root[ver]可以直接赋值,不需要再Merge了。
  • autoint
    你对可持久化的讲解还真是精辟
  • fengsongquan
    fhq treap 大法吼啊!!!
  • 可口可乐头
    fhq treap 大法吼啊!!!
  • overflow
    fhq是谁
  • Sai_0511
    范浩强
作者: 大奕哥 更新时间: 2017-12-04 15:44  在Ta的博客查看    11  

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;
}

评论

  • Chjka
    mod QWJ
  • Delva
    %%%
  • a999999
    TQL
  • 白哥小葱
    我看到了什么!!!洛谷O2优化
  • autoint
    @白哥小葱 所以呢?
  • EternalAlexander
    码风差评
  • 千年之狐_天才
    @白哥小葱 你怕不是个小学生
作者: 苏联元帅 更新时间: 2018-03-08 00:29  在Ta的博客查看    11  

可持久化01trie树 将数字表示成二进制,即可用01trie树来保存维护数字的集合. trie树每个节点存0,1儿子以及集合大小.

本题中数字可能是负数,为了处理方便,存储时都加一个大常数将数字统一为正的,取出数字时再减掉即可.

本题所用trie树的深度为32,两次版本变化的只有一条长度为32的链,故可以仿照主席树重用之前节点的思路,将指针指回之前的节点,只新建本次用到的节点,使空间复杂度保持在O(qw),w为位长,所有操作时间复杂度均为O(w).

// luogu-judger-enable-o2
#include <stdio.h>
#include <iostream>
using namespace std;
const int maxt=6e5*32;
const int maxn=6e5;
int ch[maxt][2]={0},size[maxt]={0};
int mem=0,root[maxn];
void insert(int& x,int y,int v)
{
    x=++mem;
    v+=1e9;
    size[x]=size[y]+1;
    int p=x,q=y;
    for(int i=31;i>=0;i--)
    {
        if(v&(1<<i))
        {
            ch[p][1]=++mem;
            ch[p][0]=ch[q][0];

            p=ch[p][1];
            q=ch[q][1];
        }
        else
        {
            ch[p][0]=++mem;
            ch[p][1]=ch[q][1];

            p=ch[p][0];
            q=ch[q][0];
        }
        size[p]=size[q]+1;
    }
}
void erase(int& x,int y,int v)
{
    int q=y;
    v+=1e9;

    for(int i=31;i>=0;i--)
    {
        if(v&(1<<i))
            q=ch[q][1];
        else
            q=ch[q][0];
        if(!q||!size[q])
        {
            x=y;
            return;
        }
    }
    x=++mem;
    size[x]=size[y]-1;
    int p=x;
    q=y;
    for(int i=31;i>=0;i--)
    {
        if(v&(1<<i))
        {
            ch[p][1]=++mem;
            ch[p][0]=ch[q][0];

            p=ch[p][1];
            q=ch[q][1];
        }
        else
        {
            ch[p][0]=++mem;
            ch[p][1]=ch[q][1];

            p=ch[p][0];
            q=ch[q][0];
        }
        size[p]=size[q]-1;
    }
}
int getsmaller(int x,int v)
{
    v+=1e9;
    int p=x;
    int ret=0;
    for(int i=31;i>=0;i--)
    {
        if(v&(1<<i))
        {
            ret+=size[ch[p][0]];
            p=ch[p][1];
        }
        else
            p=ch[p][0];
        if(!p||!size[p])
            return ret;
    }
    return ret;
}
int getbigger(int x,int v)
{
    v+=1e9;
    int p=x;
    int ret=0;
    for(int i=31;i>=0;i--)
    {
        if(v&(1<<i))
            p=ch[p][1];
        else
        {
            ret+=size[ch[p][1]];
            p=ch[p][0];
        }
        if(!p||!size[p])
            return ret;
    }
    return ret;
}
int getvalue(int x,int rank)
{
    int p=x;
    int ret=-1e9;
    for(int i=31;i>=0;i--)
    {
        if(rank>size[ch[p][0]])
        {
            rank-=size[ch[p][0]];
            p=ch[p][1];
            ret+=(1<<i);
        }
        else
            p=ch[p][0];
    }
    return ret;
}
int n,his=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int v,opt,x;
        scanf("%d%d%d",&v,&opt,&x);
        if(opt==1)
            insert(root[i],root[v],x);
        else if(opt==2)
            erase(root[i],root[v],x);
        else if(opt==3)
        {
            root[i]=root[v];
            cout<<getsmaller(root[v],x)+1<<endl;
        }
        else if(opt==4)
        {
            root[i]=root[v];
            cout<<getvalue(root[v],x)<<endl;
        }
        else if(opt==5)
        {
            root[i]=root[v];
            int sm=getsmaller(root[v],x);
            if(!sm)
                cout<<-2147483647<<endl;
            else
                cout<<getvalue(root[v],sm)<<endl;
        }
        else
        {
            root[i]=root[v];
            int gm=getbigger(root[v],x);
            if(!gm)
                cout<<2147483647<<endl;
            else
                cout<<getvalue(root[v],size[root[v]]-gm+1)<<endl;
        }
    }
    return 0;
}

评论

  • yijan
    非常抱歉,opt == 2 时 条件应该改为if(it!=nums[i]->end()&&*it == x) 否则会RE!(感觉着算数据的锅吧)
  • Simpson561
    我开了O2写了bac映射似乎还是T两个点……
  • little_gift
    Simpson!
  • wxq1229
    最简单的一篇。。。。。。。
作者: yijan 更新时间: 2018-10-07 12:42  在Ta的博客查看    10  

以rope实现的,很简单的可持久数组。
由于只是个数组,开5e5个显然会炸空间,所以这是篇部分分的题解。

rope是什么?STL的内置的可持久化的数组。其最为方便的就是可以O1复制原来的数组。事实上rope的内置实现也是平衡树,由于只需要复制根结点,O1可以做到复制历史版本。

然而这个东西不开O2会被卡T四个点!

实现思路非常简单,对于一个新的操作,先复制其上一个操作的版本(O1!)然后进行操作。

我们保证每个版本中的数字都是有序的,然后每次插入需要二分寻找插入位置,二分寻找删除位置,二分寻找前驱后缀,对于查排名就更简单了,由于是有序的,直接 begin() + rank 就可以得到。为了实现方便,选择使用STL中的lowerbound和upperbound,很慢是肯定的。对于题目中范围不大不需要太优秀的时候可以采用这种方法,四十行不到实现可持久平衡树。

科普一下rope基本操作(百度貌似有点难找):

#include<ext/rope>
using namespace __gnu_cxx;//rope的命名空间
rope<type> R;
R.push_back(a) //往后插入
R.insert(pos,a)//在pos位置插入a,pos是一个迭代器。
R.erase(pos,n)//在pos位置删除n个元素。
R.replace(pos,x)//从pos开始替换成x
R.substr(pos,x)//从pos开始提取x个。
//多数时候定义rope用指针(方便可持久化) 所以上面的点多数时候要换成->

如何进行复制?很简单,一句话:

rope<type>* R[1000];
R[i] = new rope<type>(*R[v]);

在上部分分代码前先说一下如何对其优化空间,我们发现查询操作对原数组不改变,于是可以开个bac数组查询操作直接映射到查询前的版本(两个版本一样),就可以少开写空间。但是yijan太懒了懒得写。。于是只有一个80分代码贴在这里:

/*Heroes Never Die!*/
#include "ext/rope"
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
using namespace __gnu_cxx;
#define MAXN 500006
rope<int> *nums[MAXN];int n;
int main(){
    cin >> n;
    nums[0] = new rope<int>();
    for(int i=1;i<=n;++i){
        static int v,opt,x;
        scanf("%d%d%d",&v,&opt,&x);
        nums[i] = new rope<int>(*nums[v]);
        if(opt == 1)
            nums[i]->insert(lower_bound(nums[i]->begin(),nums[i]->end(),x)-nums[i]->begin(),x);
        if(opt == 2){
            auto it = lower_bound(nums[i]->begin(),nums[i]->end(),x);
            if(*it == x) nums[i]->erase(it-nums[i]->begin(),1);
        }
        if(opt == 3)
            printf("%d\n",(int)(lower_bound(nums[i]->begin(),nums[i]->end(),x)-nums[i]->begin()) + 1);
        if(opt == 4)
            printf("%d\n",*(nums[i]->begin() + x - 1));
        if(opt == 5){
            auto it = lower_bound(nums[i]->begin(),nums[i]->end(),x);
            if(it == nums[i]->begin() - 1) puts("-2147483647");
            else --it,printf("%d\n",*it);
        }
        if(opt == 6){
            auto it = upper_bound(nums[i]->begin(),nums[i]->end(),x);
            if(it == nums[i]->end()) puts("2147483647");
            else printf("%d\n",*it);
        }
    }
}

评论

  • GKxx
    Orz
  • yijan
    66orz
  • wycero
    orzCLZ
作者: 小粉兔 更新时间: 2018-11-27 16:02  在Ta的博客查看    4  

题意简述:

题面说的很清楚了。

题解:

考虑建立一棵每个节点都表示一个版本的树。

以初始版本 $0$ 为根。对于第 $i$ 个操作,从 $v_i$ 向 $i$ 连一条边,而边权则是 $opt_i$ 和 $x_i$ 的二元组,表示经过这条边上操作,可以达到下一个状态。

考虑使用权值树状数组维护操作。只需要实现单点加,查询前缀和以及树状数组上二分的操作即可。

树状数组提前插入 $-2147483647$ 和 $2147483647$ 两个数,方便统计。

因为权值范围太大,所以先离散化权值,再插入树状数组。

只需要从结点 $0$ 开始 DFS ,进入子树时执行操作,退出子树时撤销操作即可。

#include <cstdio>
#include <algorithm>
using namespace std;

const int INF = 0x7fffffff;
const int MQ = 500010;

int N, Q;
int faz[MQ], opt[MQ], a[MQ], b[MQ];
int Ans[MQ];

int eh[MQ], nxt[MQ], to[MQ], tot;
inline void ins(int x, int y) {
    nxt[++tot] = eh[x]; to[tot] = y; eh[x] = tot;
}

int B[MQ];
inline void Add(int i, int x) { for (; i <= N; i += i & -i) B[i] += x; }
inline int Qur(int i) { int A = 0; for (; i; i -= i & -i) A += B[i]; return A; }
inline int BS(int x) { int p = 0; for (int j = 1 << 18; j; j >>= 1) if ((p | j) <= N && B[p | j] <= x) x -= B[p |= j]; return p;}

void DFS(int u, int o, int x) {
    int ok = 1;
    if (o == 1) Add(x, 1);
    if (o == 2) {
        if (Qur(x) == Qur(x - 1)) ok = 0;
        else Add(x, -1);
    }
    if (o == 3) Ans[u] = Qur(x - 1);
    if (o == 4) Ans[u] = b[BS(x) + 1];
    if (o == 5) Ans[u] = b[BS(Qur(x - 1) - 1) + 1];
    if (o == 6) Ans[u] = b[BS(Qur(x)) + 1];

    for (int i = eh[u]; i; i = nxt[i])
        DFS(to[i], opt[to[i]], a[to[i]]);

    if (o == 1) Add(x, -1);
    if (o == 2 && ok) Add(x, 1);
}

int main() {
    scanf("%d", &Q);
    for (int i = 1; i <= Q; ++i) {
        scanf("%d%d%d", &faz[i], &opt[i], &a[i]);
        if (opt[i] != 4)
            b[++N] = a[i];
    } b[++N] = -INF, b[++N] = INF;
    sort(b + 1, b + N + 1);
    N = unique(b + 1, b + N + 1) - b - 1;
    for (int i = 1; i <= Q; ++i) {
        ins(faz[i], i);
        if (opt[i] != 4)
            a[i] = lower_bound(b + 1, b + N + 1, a[i]) - b;
    }
    Add(1, 1), Add(N, 1);
    DFS(0, 0, 0);
    for (int i = 1; i <= Q; ++i) {
        if(opt[i] > 2)
            printf("%d\n", Ans[i]);
    }
    return 0;
}

评论

  • 还没有评论
作者: ywy_c_asm 更新时间: 2018-11-22 22:05  在Ta的博客查看    3  

在学替罪羊树的时候发现网上大部分博客都有这么一句话:

“缺点:可持久化困难。”

感觉可持久化替罪羊挺好写的啊……反正我不会$fhq\space Treap$……

我们知道可持久化数据结构的套路就是修改的时候边走边新建节点挂成链,比如主席树、可持久化$Trie$,我们一般是这样进行的,修改的时候递归操作,对当前节点复制一份,把不用访问的儿子指向原来节点的儿子(这样就节约了空间),然后要访问的那个儿子就递归下去。

我们发现这个用在线段树上面非常合适,因为他的祖先与后代的关系是恒定不变的,而平衡树就不太一样了。一般的平衡树都过于灵活,变化比较复杂,这主要是因为大部分平衡树都得旋转然后就父子关系乱伦,我们的可持久化的核心在于几个父亲共用一个儿子,所以$Splay$什么的不可持久化……

然后不旋转的平衡树在$OI$中主要有两种:$fhq\space Treap$(然而我并不会)和替罪羊树。我们考虑把替罪羊树按照上面那种方式可持久化。

但是我们发现了一个严重的问题,这个替罪羊树虽然并不用旋转,但他的核心在于暴力拍扁重构,这样做可能会给父亲换掉一个儿子,然后这种多父一子的持久化关系就乱了。

其实我们发现重构也是暴力重构的,我们知道替罪羊树的一系列操作在时间上是均摊$O(nlogn)$的,我们原来进行可持久化的思路是在一条链的修改操作(单纯的插入删除)上进行节点复制挂成新的一条链,这样因为替罪羊树的树高本来就因为暴力重构比较平衡可以看做是$O(logn)$级别的,每次插入一条长度为树高级别的链,所以新建的节点个数是$O(nlogn)$级别的。然后我们现在在暴力重构的时候也进行节点的复制,让重构不影响原来的版本,仅影响当前的版本,然后就相当于所有修改操作都要复制一次节点,所以空间复杂度与其时间复杂度相当仍然是$O(nlogn)$的,并不会爆炸。

这么着看上去非常暴力,不过我写的可持久化替罪羊树在时间和空间上实测比很多人的$fhq\space Treap$的常数要小……替罪羊树真是个好东西……

上代码~

#include<iostream>
#include<cstdio>
#include<cstring>
#define alpha (double)0.7//alpha设为0.7比较好
#define inf 2147483647
using namespace std;
namespace ywy
{
    inline int get()
    {
        int n=0;
        char c;
        while((c=getchar())||23333)
        {
            if(c>='0'&&c<='9')break;
            if(c=='-')goto s;
        }
        n=c-'0';
        while((c=getchar())||23333)
        {
            if(c>='0'&&c<='9')n=n*10+c-'0';
            else return(n);
        }
s:
        while((c=getchar())||23333)
        {
            if(c>='0'&&c<='9')n=n*10-c+'0';
            else return(n);
        }
    }
    void print(int num)
    {
        if(num<0)putchar('-'),num=-num;
        if(num>=10)print(num/10);
        putchar(num%10+'0');
    } int data[30000001],ch[30000001][2],cnt[30000001],size[30000001],gn=1;
    inline void up(int tree)
    {
        size[tree]=size[ch[tree][0]]+size[ch[tree][1]]+cnt[tree];
    } int nd[500001],ptr=1;
    void dfs(int tree)//在重构前先把子树的点找出来
    {
        if(!tree)return;
        dfs(ch[tree][0]);
        if(cnt[tree])nd[ptr]=tree,ptr++;
        dfs(ch[tree][1]);
    }
    int digui(int l,int r)//暴力重构成高度严格logn的子树,注意仍然要进行节点复制
    {
        if(l>r)return(0);
        int mid=(l+r)>>1;
        int tree=nd[mid];
        int me=gn;
        gn++;
        data[me]=data[tree];
        cnt[me]=cnt[tree];
        ch[me][0]=digui(l,mid-1);
        ch[me][1]=digui(mid+1,r);
        up(me);
        return(me);
    } int root[500001];
    int insert(int old,int num)//插入
    {
        int tree=gn;
        gn++;
        data[tree]=data[old];
        cnt[tree]=cnt[old];
        size[tree]=size[old]+1;//节点复制
        if(!old||data[old]==num)
        {
            data[tree]=num;
            ch[tree][0]=ch[old][0];
            ch[tree][1]=ch[old][1];//注意不需要递归的时候记得把两个儿子都指一下
            cnt[tree]++;
            return(tree);
        }
        int op=num>data[tree];
        ch[tree][op^1]=ch[old][op^1];
        ch[tree][op]=insert(ch[old][op],num);
        if((double)max(size[ch[tree][0]],size[ch[tree][1]])>(double)size[tree]*alpha)
        {
            ptr=1;
            dfs(tree);
            return(digui(1,ptr-1));
        }
        return(tree);
    }
    int del(int old,int num)//删除,也要进行节点复制
    {
        int tree=gn;
        gn++;
        data[tree]=data[old];
        size[tree]=size[old]-1;
        cnt[tree]=cnt[old];
        if(num==data[tree])
        {
            cnt[tree]--;
            ch[tree][0]=ch[old][0];
            ch[tree][1]=ch[old][1];
            return(tree);
        }
        int op=num>data[tree];
        ch[tree][op^1]=ch[old][op^1];
        ch[tree][op]=del(ch[old][op],num);
        return(tree);
    }
    int rankof(int tree,int rk)//剩下的跟普通平衡树就一样了~
    {
        if(rk<=size[ch[tree][0]])return(rankof(ch[tree][0],rk));
        rk-=size[ch[tree][0]];
        if(rk<=cnt[tree])return(data[tree]);
        rk-=cnt[tree];
        return(rankof(ch[tree][1],rk));
    }
    inline int getrank(int num,int tree)
    {
        int ans=1,cur=tree;
        while(cur&&data[cur]!=num)
        {
            if(num>data[cur])ans+=cnt[cur]+size[ch[cur][0]],cur=ch[cur][1];
            else cur=ch[cur][0];
        }
        ans+=size[ch[cur][0]];
        return(ans);
    } inline int find(int tree,int num)
    {
        int cur=tree;
        while(cur&&data[cur]!=num)cur=ch[cur][num>data[cur]];
        if(!cnt[cur])return(inf);
        return(cur);
    }
    void ywymain()
    {
        int n=get();
        for(register int i=1; i<=n; i++)
        {
            int ver=get(),cmd=get(),x=get();
            if(cmd==1)
            {
                root[i]=insert(root[ver],x);
            }
            if(cmd==2)
            {
                if(find(root[ver],x)==inf)root[i]=root[ver];
                else root[i]=del(root[ver],x);
            }
            if(cmd==3)
            {
                root[i]=root[ver];
                print(getrank(x,root[i]));
                putchar('\n');
            }
            if(cmd==4)
            {
                root[i]=root[ver];
                print(rankof(root[i],x));
                putchar('\n');
            }
            if(cmd==5)
            {
                root[i]=root[ver];
                int cjr=getrank(x,root[i]);
                if(cjr==1)print(-inf);
                else print(rankof(root[i],cjr-1));
                putchar('\n');
            }
            if(cmd==6)
            {
                root[i]=root[ver];
                int me=find(root[i],x),rk;
                if(me==inf)rk=getrank(x,root[i]);
                else rk=getrank(x,root[i])+cnt[me];
                if(rk>size[root[i]])print(inf);
                else print(rankof(root[i],rk));
                putchar('\n');
            }
        }
    }
}
int main()
{
    ywy::ywymain();
    return(0);
}