用 Trie 树写的，28分求助 评测记录

#include<bits/stdc++.h>
using namespace std;
int n,inf=1e9;
int root[500005],tr[2][16000005],val[16000005],cnt=1;
bool is;
void insert(int x,int v,int i,int od){
    int now=root[i]=++cnt;
    int old=root[od];val[now]=val[old]+v;
    for(int i=30;i>=0;i--){
        tr[0][now]=tr[0][old];
        tr[1][now]=tr[1][old];
        now=tr[(x>>i)&1][now]=++cnt;
        old=tr[(x>>i)&1][old];
        val[now]=val[old]+v;
        if(val[now]<0)is=1;
    }
}
inline int query(int k,int v){
    int res=0,now=root[v];
    for(int i=30;i>=0;i--){
        res<<=1;
        if(val[tr[0][now]]>=k)now=tr[0][now];
        else{
            res|=1;
            k-=val[tr[0][now]];
            now=tr[1][now];
        }
    }
    if(res>2e9)return 2147483647;
    if(res==0)return -2147483647;
    return res-inf;
}
inline int find(int x,int v){
    int res=1,now=root[v];
    for(int i=30;i>=0&&now;i--){
        if((x>>i)&1){
            res+=val[tr[0][now]];
            now=tr[1][now];
        }else now=tr[0][now];
    }
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int v,op,x;
        scanf("%d%d%d",&v,&op,&x);
        if(op==1)insert(x+inf,1,i,v);
        else if(op==2)insert(x+inf,-1,i,v);
        else if(op==3)printf("%d\n",find(x+inf,v));
        else if(op==4)printf("%d\n",query(x,v));
        else if(op==5)printf("%d\n",query(find(x+inf,v)-1,v));
        else if(op==6)printf("%d\n",query(find(x+inf+1,v),v));
        if(op>2)root[i]=root[v];
        if(op==2&&is)is=0,insert(x+inf,1,i,v);
//      printf("%d : ",i);
//      put(root[i],0),putchar('\n');
    }

    return 0;
}