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

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

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

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

评论

  • SovietPower
    一点(很小的)优化? 操作3.4.5.6都不会改原树,root[i]=root[ver]可以直接赋值,不需要再Merge了。
作者: 大奕哥 更新时间: 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;
}

评论

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

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

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

如果用值来当做区间左右端点,每个叶子节点上存某个值出现的次数,非叶子节点上存一定范围内的值出现的总次数,就可以建成值域线段树。可以在上面直接查询第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;
}

评论

  • 还没有评论
作者: 龙之吻—水货 更新时间: 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;
            }
        }
    }   
}

评论

  • Chjka
    mod QWJ
  • Delva000
    %%%
  • a999999
    TQL
作者: 苏联元帅 更新时间: 2018-03-08 00:29  在Ta的博客查看    3  

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

评论

  • 还没有评论
作者: GKxx 更新时间: 2018-07-24 11:05  在Ta的博客查看    0  

昨天晚上用zkw线段树过了P3369普通平衡树,突然意识到如果让线段树可持久化不就可以过这道题了吗!于是我就把这道题A了。。。

看到题解里果然已经有人用线段树了,不过我们的用法还是略有不同,我是将读入的数据离散化的。

线段树的做法很简单。设f[x]表示x这个数出现了多少次:

  • 插入一个数:++f[x]

  • 删除一个数:--f[x]

  • 查询一个数的排名:求前缀和

  • 查询第k小:在线段树上二分

  • 前驱、后继:转化为先查询排名再查询第k小。(昨晚做普通平衡树的时候是用zkw写的,前驱和后继就比较方便,但是这题要可持久化,得动态开点,为了避免麻烦就这样写了)

所以我们的线段树只要维护f数组的区间和就行了!

这题要可持久化,那么只要对线段树可持久化就好了,非常简单。

另外,千万要注意的一个事情就是本题的2操作不保证被删除的数存在,所以sum数组的维护一定要仔细考虑。我一开始就是在这个地方WA到只有28分,然后第一次改完依然只有80分,又静态查错了好久才发现问题。

// C++11
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>

template <typename T> inline void read(T& t) {
    int f = 0, c = getchar(); t = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
    if (f) t = -t;
}
template <typename T, typename... Args>
inline void read(T& t, Args&... args) {
    read(t); read(args...);
}

#define rep(I, A, B) for (int I = (A); I <= (B); ++I)
#define rrep(I, A, B) for (int I = (A); I >= (B); --I)

const int maxn = 5e5 + 100;
struct Command {
    int v, q, x;
    explicit Command(int vv = 0, int qq = 0, int xx = 0)
        : v(vv), q(qq), x(xx) {}
};
Command cmd[maxn];
int tmp[maxn];
int root[maxn], sum[maxn * 40], left[maxn * 40], right[maxn * 40];
int n, tot, all;

void build(int &curr, int l, int r) {
    curr = ++tot;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(left[curr], l, mid);
    build(right[curr], mid + 1, r);
}
void insert(int &curr, int pre, int l, int r, int x, int val) {
    curr = ++tot;
    sum[curr] = sum[pre];
    if (l == r) {
        sum[curr] += val;
        if (sum[curr] < 0) sum[curr] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        right[curr] = right[pre];
        insert(left[curr], left[pre], l, mid, x, val);
    } else {
        left[curr] = left[pre];
        insert(right[curr], right[pre], mid + 1, r, x, val);
    }
    sum[curr] = sum[left[curr]] + sum[right[curr]];
}
int querySum(int curr, int l, int r, int x) {
    if (x < l) return 0;
    if (x >= r) return sum[curr];
    int mid = (l + r) >> 1;
    return querySum(left[curr], l, mid, x) + querySum(right[curr], mid + 1, r, x);
}
int queryKth(int curr, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (k <= sum[left[curr]])
        return queryKth(left[curr], l, mid, k);
    else
        return queryKth(right[curr], mid + 1, r, k - sum[left[curr]]);
}
inline int queryPrev(int v, int x) {
    int lessthan = querySum(root[v], 1, all, x - 1);
    if (!lessthan) return -2147483647;
    else return tmp[queryKth(root[v], 1, all, lessthan)];
}
inline int querySucc(int v, int x) {
    int lesseq = querySum(root[v], 1, all, x);
    if (lesseq >= sum[root[v]]) return 2147483647;
    else return tmp[queryKth(root[v], 1, all, lesseq + 1)];
}

int main() {
    read(n);
    rep(i, 1, n) {
        read(cmd[i].v, cmd[i].q, cmd[i].x);
        if (cmd[i].q != 4)
            tmp[++all] = cmd[i].x;
    }
    std::sort(tmp + 1, tmp + all + 1);
    all = std::unique(tmp + 1, tmp + all + 1) - (tmp + 1);

    build(root[0], 1, all);

    rep(i, 1, n) {
        int v = cmd[i].v, q = cmd[i].q, x = cmd[i].x;
        if (q != 4)
            x = std::lower_bound(tmp + 1, tmp + all + 1, x) - tmp;
        root[i] = root[v];
        switch (q) {
            case 1:
                insert(root[i], root[v], 1, all, x, 1);
                break;
            case 2:
                insert(root[i], root[v], 1, all, x, -1);
                break;
            case 3:
                printf("%d\n", querySum(root[i], 1, all, x - 1) + 1);
                break;
            case 4:
                printf("%d\n", tmp[queryKth(root[i], 1, all, x)]);
                break;
            case 5:
                printf("%d\n", queryPrev(i, x));
                break;
            case 6:
                printf("%d\n", querySucc(i, x));
                break;
        }
    }
    return 0;
}