题目描述

fhq treap

样例

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
struct node{
    int l,r,val,key,size;
}tr[N];
int idx,root,n;

int new_node(int v){
    tr[++idx].val = v;
    tr[idx].key = rand();
    tr[idx].size = 1;
    return idx;
}

void pushup(int u){
    tr[u].size = tr[tr[u].l].size+tr[tr[u].r].size+1;
}

void split(int p,int v,int &x,int &y){
    if(!p){
        x = y = 0;
        return; 
    }
    if(tr[p].val<=v){
         x = p;
         split(tr[x].r,v,tr[x].r,y);
    }
    else {
        y= p;
        split(tr[y].l,v,x,tr[y].l);
    }
    pushup(p);
}

int merge(int x,int y){
    if(!x||!y) return x+y;
    if(tr[x].key<tr[y].key){
        tr[x].r = merge(tr[x].r,y);
        pushup(x);
        return x;
    }
    else {
        tr[y].l= merge(x,tr[y].l);
        pushup(y);
        return y;
    }
}

void insert(int v){
    int x,y,z;
    split(root,v,x,y);
    z = new_node(v);
    // cout<<"插入"<<tr[z].val<<endl;
    root = merge(merge(x,z),y);
}

void del(int v){
    int x,y,z;
    split(root,v,x,y);
    split(x,v-1,x,z);
    // cout<<"删除"<<tr[z].val<<endl;
    z = merge(tr[z].l,tr[z].r);
    root = merge(merge(x,z),y);
}

int get_k(int x,int k){
    int u = x;
    while(1){
        if(tr[tr[u].l].size>=k) u =tr[u].l;
        else if(tr[tr[u].l].size+1==k) return u;
        else k-=tr[tr[u].l].size+1,u = tr[u].r;
    }
}

int get_rank(int v){
    int x,y,z;
    split(root,v-1,x,y);
    z = tr[x].size;
    root = merge(x,y);
    return z+1;
}

void pre(int v){
    int x,y;
    split(root,v-1,x,y);
    cout<<tr[get_k(x,tr[x].size)].val<<endl;
    root = merge(x,y);
}

void next(int v){
    int x,y;
    split(root,v,x,y);
    cout<<tr[get_k(y,1)].val<<endl;
    root = merge(x,y);
}


int main(){
    cin>>n;
    while(n--){
        int op,x;
        cin>>op>>x;
        if(op==1){
            insert(x);
        }
        if(op==2)del(x);
        if(op==3){
            cout<<get_rank(x)<<endl;
        } 
        if(op==4){
            cout<<tr[get_k(root,x)].val<<endl;
        }
        if(op==5)pre(x);
        if(op==6)next(x);
    }
}