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

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

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

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

评论

  • Chjka
    mod QWJ
  • Delva
    %%%
  • a999999
    TQL
  • 白哥小葱
    我看到了什么!!!洛谷O2优化
  • autoint
    @白哥小葱 所以呢?
作者: 苏联元帅 更新时间: 2018-03-08 00:29  在Ta的博客查看    7  

可持久化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;
}

评论

  • hehe_54321
    开头的 #define mid ((l+r)>>1) 对于负数的操作让人迷惑,但是事实证明这不会造成无限递归,但是写成 l+((r-l)>>1) 更清晰
  • 蹲在丛中笑
    巨啊
作者: hehe_54321 更新时间: 2018-03-08 17:58  在Ta的博客查看    5  

这个题也是可以用可持久化线段树来解决的。

值域线段树(也有的叫权值线段树)可以用来维护一个可重集,并实现一些一般情况下平衡树才能实现的事情。

如果用值来当做区间左右端点,每个叶子节点上存某个值出现的次数,非叶子节点上存一定范围内的值出现的总次数,就可以建成值域线段树。可以在上面直接查询第k大值、小于某值的数的个数等等,具体请百度或参见代码。

如何将线段树可持久化呢?线段树在单点更新的时候会经过log n个节点,每一次更新时显然也只有这么多节点会发生变化。

记录每一个版本的线段树的根节点,每一次操作前将根节点赋为与这次操作基于的版本的根节点相同。在更新操作时,备份每一个经过的节点(包括各个属性:左、右子树以及区间和),然后再进行修改。具体也可以参考可持久化线段树的题解。

如果直接用可持久化的值域线段树,显然空间是不够的(4*2e9个节点啊...)。现在有两种选择:

1.发现这道题没有加、减操作,所有操作涉及的值都是确定的。因此可以进行离散化,然后再做,想必可以A掉吧(我没试过)

2.可以写动态开点线段树。题目要求的集合一开始是空的,因此如果一开始建一棵完整的线段树的话,每一个节点记录的区间和都是0。而总共只有5e5次操作,每一次操作涉及更改节点最多有log2(2e9)=31个,两者乘起来远远小于4*2e9。

可以考虑一开始不真正建树。规定:如果某节点的某个子节点是一个特殊的标记的话,表明以这个子节点为根的子树还没有实际建出来。显然,一个子树没有实际建出来的时候,其表示的区间的和为0。(以下代码中我用的标记是0)

在进行修改操作的时候,可能需要建出来要走入的那个子节点。在进行查询操作的时候,可以把未建出的子节点的区间和当做0。

附:写完后我发现前驱和后继竟然是最难写的...

附:注意各种对不存在的节点的查询/要忽略的操作

附:注意代码中有一些操作用到的变量被设置成了全局变量,还define了一个mid,表示区间中点,可能比较奇怪...

博客

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bits/stdc++.h>
#define mid ((l+r)>>1)
#define inf 2147483647
using namespace std;
int lc[20000000],rc[20000000],root[20000000],dat[20000000],ll=-1e9,rr=1e9;
//lc[i]、rc[i]分别表示节点i的左子节点、右子节点编号,如果lc[x]=0则表示x的左子树尚未建出来,rc[x]同理
//dat[i]表示节点i表示的值域区间中各数的出现次数之和
int n,L,x,mem=1;//因为0号被"未实际建出的节点"的特殊标记占用了,1号被版本0的根节点占用了

void addx(int l,int r,int& num)//更新操作,将线段树维护的集合中数L的出现次数加上x(x为1或-1)
{
    int t=num;num=++mem;lc[num]=lc[t];rc[num]=rc[t];dat[num]=dat[t];//备份当前节点,如果当前节点原来为空则也可以完成
    if(l==r)
    {
        if(!(dat[num]==0&&x<0)) dat[num]+=x;//如果L出现次数为0且操作为删除操作,则忽略操作
        return;
    }
    if(L<=mid)  addx(l,mid,lc[num]);
    else    addx(mid+1,r,rc[num]);
    dat[num]=0;
    if(lc[num]) dat[num]+=dat[lc[num]];
    if(rc[num]) dat[num]+=dat[rc[num]];//维护当前节点信息
}
int query(int l,int r,int num)//查询集合中小于x的数的个数
{
    if(l==r)    return 0;//如果已经到叶子节点了,那么当前节点等于x,显然不小于x
    if(!num)    return 0;//如果当前节点为空,那么该节点表示的子树中数都没有,自然返回0
    if(x<=mid)  return query(l,mid,lc[num]);//根据x决定向左/右子树走
    else    return (lc[num]?dat[lc[num]]:0)+query(mid+1,r,rc[num]);
}
int query_kth(int l,int r,int k,int num)//查询第k小数
{
    assert(num!=0);//assert(x)表示如果x为false则停止程序,是用来调试的。如果查询操作是正常进行的,那么不可能走到未建出的点中
    if(l==r)    {return l;}
    //if(!num)  return 0;//没有用
    int ls=lc[num]?dat[lc[num]]:0;
    if(ls>=k)   return query_kth(l,mid,k,lc[num]);//根据左子树中数出现总次数决定向左/右子树走
    else        return query_kth(mid+1,r,k-ls,rc[num]);
}
int query_time(int l,int r,int num)//查询数x出现的次数
{
    while(l!=r)
    {
        if(!num)    return 0;//当前节点未建出,表明其子节点均未出现
        if(L<=mid)  r=mid,num=lc[num];
        else    l=mid+1,num=rc[num];
    }
    return dat[num];
}
int query_pre(int l,int r,int num)//查询数x的前驱
{
    int t=query(l,r,num);//t是集合中比x小的数的个数
    if(t==0)    return -inf;//如果集合中比x小的数有0个,则x是集合中最小的数,不存在前驱
    return query_kth(l,r,t,num);//否则查询集合中第t小即可
}
int query_nxt(int l,int r,int num)
{
    int t1=query(l,r,num),t2=query_time(l,r,num);//t1是集合中比x小的数的个数,t2是集合中x出现的次数,加起来是集合中小于等于x的数的个数
    x=inf;int t3=query(l,r,num);
    if(t1+t2==t3)   return inf;//如果集合中小于等于x的数与集合中小于等于inf的数相等,则x是集合中最大的数,不存在后继
    return query_kth(l,r,t1+t2+1,num);//否则查询集合中第t1+t2+1小即可
}
int main()
{
    int i,v,idx;
    scanf("%d",&n);
    root[0]=1;
    for(i=1;i<=n;i++)
    {
        scanf("%d%d%d",&v,&idx,&x);root[i]=root[v];
        if(idx==1)
        {
            L=x;x=1;
            addx(ll,rr,root[i]);
        }
        else if(idx==2)
        {
            L=x;x=-1;
            addx(ll,rr,root[i]);
        }
        else if(idx==3)
        {
            printf("%d\n",query(ll,rr,root[i])+1);
        }
        else if(idx==4)
        {
            printf("%d\n",query_kth(ll,rr,x,root[i]));
        }
        else if(idx==5)
        {
            L=x;
            printf("%d\n",query_pre(ll,rr,root[i]));
        }
        else if(idx==6)
        {
            L=x;
            printf("%d\n",query_nxt(ll,rr,root[i]));
        }
    }
    return 0;
}

评论

  • SovietPower
    一点(很小的)优化? 操作3.4.5.6都不会改原树,root[i]=root[ver]可以直接赋值,不需要再Merge了。
  • autoint
    你对可持久化的讲解还真是精辟
作者: 大奕哥 更新时间: 2017-12-04 15:44  在Ta的博客查看    6  

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

评论

  • A星际穿越
    a=0.5。。。大佬orz
  • 龙之吻—水货
    。。。这个a指的是两个儿子节点的大小比值,换算成正常的大概是0.66。
作者: 龙之吻—水货 更新时间: 2018-03-31 16:33  在Ta的博客查看    4  

由于替罪羊树维护平衡不是靠旋转而是靠重构,所以替罪羊树的根是不会变的,这样就可以利用替罪羊树进行可持久化了。

对于3,4,5,6操作,只需要给把要操作的根复制一遍到新根上,其他的和普通的替罪羊树一样;

对于1,2操作先把要操作的根复制一遍到新根,然后进行类似动态开点的线段树,如果要加入(删除)的值比现在节点的大,就new一个左儿子,把原来的节点的所有信息copy到左儿子上,如果要加入(删除)的值比现在节点的小同理操作右儿子,如果要加入(删除)的值等于现在的节点,就直接修改就好了(详见代码)。

然而我这个替罪羊树有个缺点,每次重构的时候不能释放空间,否则会删掉有用的节点,只能通过减少a的值用时间换空间了(如果谁有解决这个的方法,求私信告知)。 附上代码

#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn = 5e5 + 7;

const int INF = 2147483647;

double a = 0.50;

int num[1000010], sum, t[1000010];

struct Node{
    Node *leftchild, *rightchild;
    int val, cnt, size, tot, del;

    Node (int val, int cnt) :
        val(val),
        leftchild(NULL),
        rightchild(NULL),
        cnt(cnt),
        del(0),
        tot(0),
        size(cnt){}
};

Node *root[maxn], *null;

void Copy(Node *&now, Node *last) {
    if (!last) {
        now = NULL;
        return;
    }
    now->leftchild = last->leftchild;
    now->rightchild = last->rightchild;
    now->cnt = last->cnt;
    now->del = last->del;
    now->size = last->size;
    now->tot = last->tot;
    now->val = last->val;
}

void UpdateSize(Node *&now) {
    if (!now) {
        return;
    }
    now->size = now->cnt;
    now->del = now->tot;
    if (now->leftchild) {
        now->size += now->leftchild->size;
        now->del += now->leftchild->del;
    }
    if (now->rightchild) {
        now->size += now->rightchild->size;
        now->del += now->rightchild->del;
    }
}

void DFS(Node *now) {
    if (!now) {
        return;
    }
    DFS(now->leftchild);
    if (now->cnt - now->tot) {
        num[++sum] = now->val;
        t[sum] = now->cnt - now->tot;       
    }
    DFS(now->rightchild);
}

Node *Rebuild(int l, int r) {
    Node *now;
    if (l > r) {
        return NULL;
    }
    if (l == r) {
        now = new Node(num[l], t[l]);
        return now;
    }
    int mid = l + r >> 1;
    now = new Node(num[mid], t[mid]);
    now->leftchild = Rebuild(l, mid - 1);
    now->rightchild = Rebuild(mid + 1, r);
    UpdateSize(now);
    return now;
}

void Maintain(Node *&now) {
    if (!now) {
        return;
    }
    int left_size = now->leftchild ? now->leftchild->size : 0;
    int right_size = now->rightchild ? now->rightchild->size : 0;
    if ((double)left_size * a > (double)right_size) {
        sum = 0;
        DFS(now);
        now = Rebuild(1, sum);
    }
    else if ((double)right_size * a > (double)left_size) {
        sum = 0;
        DFS(now);
        now = Rebuild(1, sum);
    }
    else if(now->del >= now->size / 2 || now->cnt <= now->tot) {
        sum = 0;
        DFS(now);
        now = Rebuild(1, sum);      
    }
}

Node *Insert(Node *now, int val, Node *last) {
    if (!now) {
        now = new Node(val, 1);
        return now;
    }
    if (now->val == val) {
        now->cnt++;
    }
    else if(now->val > val) {
        now->leftchild = new Node(1, 1);
        Copy(now->leftchild, last->leftchild);
        now->leftchild = Insert(now->leftchild, val, last->leftchild);
    }
    else {
        now->rightchild = new Node(1, 1);
        Copy(now->rightchild, last->rightchild);
        now->rightchild = Insert(now->rightchild, val, last->rightchild);
    }
    UpdateSize(now);
    Maintain(now);
    return now;
}

Node *Remove(Node *now, int val, Node *last) {
    if (!now) {
        return now;
    }
    if (now->val == val) {
        now->tot++;
    }
    else if (now->val > val) {
        now->leftchild = new Node(1, 1);
        Copy(now->leftchild, last->leftchild);
        now->leftchild = Remove(now->leftchild, val, last->leftchild); 
    }
    else {
        now->rightchild = new Node(1, 1);
        Copy(now->rightchild, last->rightchild);
        now->rightchild = Remove(now->rightchild, val, last->rightchild);
    } 
    UpdateSize(now);
    Maintain(now);
    return now;
}

int Rank(Node *now, int val) {
    if (!now) {
        return 1;
    }
    int left_size = now->leftchild ? now->leftchild->size - now->leftchild->del: 0;
    if (now->val == val) {
        return left_size + 1;
    }
    if (now->val < val) {
        return left_size + now->cnt - now->tot + Rank(now->rightchild, val);
    }
    else {
        return Rank(now->leftchild, val);
    }
}

int FindKth(Node *now, int rank) {
    if (!now) {
        return 0;
    }
    int left_size = now->leftchild ? now->leftchild->size - now->leftchild->del: 0;
    if (rank <= left_size) {
        return FindKth(now->leftchild, rank);
    }
    rank -= left_size;
    if (rank <= now->cnt - now->tot) {
        return now->val;
    }
    rank -= now->cnt - now->tot;
    return FindKth(now->rightchild, rank);
}

int GetPro(Node *now, int val) {
    if(!now) {
        return -INF;
    }
    if (now->val < val) {
        if (now->cnt > now->tot) {
            return max(now->val, GetPro(now->rightchild, val));         
        }
        return GetPro(now->rightchild, val);
    }
    else {
        return GetPro(now->leftchild, val);
    }
}

int GetSuc(Node *now, int val) {
    if (!now) {
        return INF;
    }
    if (now->val > val) {
        if (now->cnt > now->tot) {
            return min(now->val, GetSuc(now->leftchild, val));          
        }
        return GetSuc(now->leftchild, val);
    }
    else {
        return GetSuc(now->rightchild, val);
    }
}

int n;

int main() {
    scanf("%d", &n);
    int _sum = 0;
    for (int i = 1; i <= n; i++) {
        int flag, x, numb;
        scanf("%d %d %d", &numb, &flag, &x);
        switch(flag) {
            case 1 : {
                root[++_sum] = new Node(1, 1);
                Copy(root[_sum], root[numb]);
                root[_sum] = Insert(root[_sum], x, root[numb]);
                break;
            }
            case 2 : {
                root[++_sum] = new Node(1, 1);
                Copy(root[_sum], root[numb]);
                root[_sum] = Remove(root[_sum], x, root[numb]);
                break;
            }
            case 3 : {
                root[++_sum] = new Node(1, 1);
                Copy(root[_sum], root[numb]);
                printf("%d\n", Rank(root[_sum], x));
                break;
            }
            case 4 : {
                root[++_sum] = new Node(1, 1);
                Copy(root[_sum], root[numb]);
                printf("%d\n", FindKth(root[_sum], x));
                break;
            }
            case 5 : {
                root[++_sum] = new Node(1, 1);
                Copy(root[_sum], root[numb]);
                printf("%d\n", GetPro(root[_sum], x));
                break;
            }
            case 6 : {
                root[++_sum] = new Node(1, 1);
                Copy(root[_sum], root[numb]);
                printf("%d\n", GetSuc(root[_sum], x));
                break;
            }
        }
    }   
}

评论

  • cppascalinux
    orz%%%
作者: GGN_2015 更新时间: 2018-09-29 19:54  在Ta的博客查看    2  

”一道可持久化数据结构的题,如果不强制在线,那么它八成不是一道真正的可持久化数据结构的题。“ —— GGN_2015

惊奇地发现这道题其实并不需要任何可持久化数据结构。

我们只需要建立一颗”时光树“(我们暂且这样称呼它)。如果i时刻的平衡树是由$v_i$时刻发展而来的,那么我们就令”时光树“上i号结点的父亲为$v_i$。0号结点显然是整棵”时光树“的根结点。

维护一棵平衡树(我写的是treap),最开始的时候这是一棵空树。在”时光树“上DFS,每进入结点i时就在平衡树中进行操作i(修改数据结构或储存查询的结果),然后再依次DFS结点i的每个儿子。退出结点i时,就”撤销“这个结点对数据结构的修改。例如当$opt_i = 1$时,我们向数据结构中插入了元素$x_i$,离开结点i时,我们再把$x_i$从数据结构中删除。

比较特殊的是:当$opt_i = 2$时,删除是可能失败的。如果删除失败的话,我们在回溯的时候要特判(就是说不要把本就没被成功删除的$x_i$插入回数据结构中)。

附上代码之前先作出一个声明:我的treap的代码不支持可重集合,所以我用了一个类似pair的数据结构来储存元素(第一维存储元素的值,第二维记录操作的编号),这样可以保证treap中没有重复的元素。另外,我懒得写前去和后继的查询,所以我的”前驱“和”后继“查询是利用”排名“和”第k大“查询间接实现的。(我觉得这样写treap更好调试一些)

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

struct item {int val, id;};
bool operator < (item A, item B) {
    if(A.val != B.val) return A.val < B.val;
    return A.id < B.id;
}
bool operator == (item A, item B) {
    return A.val==B.val && A.id==B.id;
}

const int maxn = (500000 + 6)*2;
namespace treap {
    int ch[maxn][2], rnd[maxn], siz[maxn]; item key[maxn]; int ncnt;
    queue<int> Q;
    void maintain(int x) {
        siz[x] = 1 + siz[ch[x][0]] + siz[ch[x][1]];
    }
    int newnode() {
        if(!Q.empty()) {
            int x = Q.front(); Q.pop();
            ch[x][0] = ch[x][1] = rnd[x] = siz[x] = 0; key[x] = (item){0, 0};
            return x;
        }
        return ++ ncnt;
    }
    void rotate(int& x, int d) {
        int k = ch[x][d^1]; ch[x][d^1] = ch[k][d]; ch[k][d] = x;
        maintain(x); x = k; maintain(k);
    }
    void insert(int& x, item v) {
        if(x == 0) {
            x = newnode(); rnd[x] = rand(); siz[x] = 1; key[x] = v;
            return;
        }
        int d = v < key[x] ? 0 : 1; insert(ch[x][d], v);
        maintain(x);
        if(rnd[x] > rnd[ch[x][d]]) rotate(x, d^1);
    }
    int rnk(int x, item v) {
        if(x == 0) return 1;
        int lsiz = 1 + siz[ch[x][0]];
        if(v == key[x]) return lsiz;
        if(v < key[x]) return rnk(ch[x][0], v);
        else           return rnk(ch[x][1], v) + lsiz;
    }
    item kth(int x, int k) {
        if(x==0 || k<=0 || k>siz[x])
            return k<=0 ? (item){-2147483647, 0} : (item){2147483647, 0};
        int lsiz = 1 + siz[ch[x][0]];
        if(lsiz == k) return key[x];
        if(k < lsiz) return kth(ch[x][0], k);
        else         return kth(ch[x][1], k-lsiz);
    }
    int LSIZ(int x) {return 1 + siz[ch[x][0]];}
    void erase(int& x, int k) {
        if(x == 0) return; /// 删除元素时一定要特判检测是否相等
        int lsiz = 1 + siz[ch[x][0]];
        if(lsiz == k) {
            if(ch[x][0]==0 || ch[x][1]==0) {
                int tmp = x; x = ch[x][0] + ch[x][1]; Q.push(tmp);
                ch[tmp][0] = ch[tmp][1] = siz[tmp] = rnd[tmp] = 0;
                key[tmp] = (item){0, 0};
            }else {
                if(rnd[ch[x][0]] > rnd[ch[x][1]]) {
                    rotate(x, 0); erase(ch[x][0], LSIZ(ch[x][0]));
                }else {
                    rotate(x, 1); erase(ch[x][1], LSIZ(ch[x][1]));
                }
                maintain(x);
            }
            return;
        }else {
            if(k < lsiz) erase(ch[x][0], k);
            else         erase(ch[x][1], k-lsiz);
            maintain(x);
        }
    }
}

int root = 0, V[maxn], OPT[maxn], X[maxn], ANS[maxn];
namespace tree {
    vector<int> nxt[maxn];
    void addedge(int f, int t) {nxt[f].push_back(t);}
    void dfs(int x) {
        bool delsuc = 0; /// 记录删除操作是否成功
        if(OPT[x]) { /// 有操作
            if(OPT[x] == 1) { /// 插入一个元素
                treap::insert(root, (item){X[x], x});
            }else if(OPT[x] == 2) { /// 删除一个元素
                int rnk = treap::rnk(root, (item){X[x], 0}); /// 查询这个元素的排名
                int get = treap::kth(root, rnk).val; /// 得到这个元素(可能为+-inf)
                if(get == X[x]) { /// 可以删除
                    treap::erase(root, rnk); delsuc = 1;
                }
            }else if(OPT[x] == 3) { /// 查排名
                ANS[x] = treap::rnk(root, (item){X[x], 0});
            }else if(OPT[x] == 4) { /// 查第k大
                ANS[x] = treap::kth(root, X[x]).val;
            }else if(OPT[x] == 5) { /// prev
                int rnk = treap::rnk(root, (item){X[x], 0}) - 1;
                int get = treap::kth(root, rnk).val;
                ANS[x] = get;
            }else if(OPT[x] == 6) { /// next
                int rnk = treap::rnk(root, (item){X[x], 0x7f7f7f7f});
                int get = treap::kth(root, rnk).val;
                ANS[x] = get;
            }
        }
        for(int i = 0; i < (int)nxt[x].size(); i ++) {
            int t = nxt[x][i]; dfs(t); /// 递归计算
        }
        if(OPT[x] == 1) { /// 回滚插入操作
            int rnk = treap::rnk(root, (item){X[x], 0}); /// 一定有
            treap::erase(root, rnk);
        }
        if(OPT[x]==2 && delsuc) {
            treap::insert(root, (item){X[x], x});
        }
    }
}

int main() {
    //freopen("nontime.in", "r", stdin);
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
        scanf("%d%d%d", &V[i], &OPT[i], &X[i]);
        tree::addedge(V[i], i);
    }
    tree::dfs(0);
    for(int i = 1; i <= n; i ++) {
        if(OPT[i]>=3) {
            printf("%d\n", ANS[i]);
        }
    }
    return 0;
}