Treap

0Zero丶紫瞳 · 2018-10-08 06:38:29 · 个人记录

#include<bits/stdc++.h>
using namespace std;

struct Treap{
    int s[2],
        val,dat,
        cnt,size;
}t[100005];
int tot,root,n,Inf=0x7ffffff;

int New(int val){
    t[++tot].val = val;
    t[tot].dat = rand();
    t[tot].cnt = t[tot].size = 1;
    return tot;
}

void Update(int p){
    t[p].size = t[t[p].s[0]].size + t[t[p].s[1]].size + t[p].cnt;
}

void Build(){
    New(-Inf);
    New(Inf);
    root = 1;
    t[1].s[1] = 2;
    Update(root);
}

int GetRankByVal(int p,int val){
    if(p == 0){
        return 0;
    }
    if(val == t[p].val){
        return t[t[p].s[0]].size+1;
    }
    if(val < t[p].val){
        return GetRankByVal(t[p].s[0] , val);
    }
    else{
        return GetRankByVal(t[p].s[1] , val) + t[t[p].s[0]].size + t[p].cnt;
    }
}

int GetValByRank(int p,int rank){
    if(p == 0)return Inf;
    if(t[t[p].s[0]].size >= rank){
        return GetValByRank(t[p].s[0],rank);
    }
    if(t[t[p].s[1]].size + t[p].cnt >= rank){
        return t[p].val;
    }
    return GetValByRank(t[p].s[1] , rank - t[t[p].s[0]].size - t[p].cnt);
}

void zig(int &p){
    int c = t[p].s[0];
    t[p].s[0] = t[c].s[1];
    t[c].s[1] = p;
    p = c;
    Update(t[p].s[1]);
    Update(p);
}

void zag(int &p){
    int c = t[p].s[1];
    t[p].s[1] = t[c].s[0];
    t[c].s[0] = p;
    p = c;
    Update(t[p].s[0]);
    Update(p);
}

void Insert(int &p, int val){
    if(p == 0){
        p = New(val);
        return;
    }
    if(val == t[p].val){
        t[p].cnt++;
        Update(p);
        return;
    }
    if(val < t[p].val){
        Insert(t[p].s[0], val);
        if(t[p].dat < t[t[p].s[0]].dat)
            zig(p);
    }
    else{
        Insert(t[p].s[1],val);
        if(t[p].dat < t[t[p].s[1]].dat)
            zag(p);
    }
    Update(p);
}

int GetPre(int val){
    int ans = 1;
    int p = root;
    while(p){
        if(val == t[p].val){
            if(t[p].s[0] > 0){
                p = t[p].s[0];
                while(t[p].s[1]){
                    p = t[p].s[1];
                }
                ans = p;
            }
            break;
        }
        if(t[p].val < val &&t[p].val > t[ans].val)
            ans = p;
        p = val < t[p].val ? t[p].s[0] : t[p].s[1];
    }
    return ans;
}

int GetNext(int val){
    int ans = 2;
    int p = root;
    while(p){
        if(val == t[p].val){
            if(t[p].s[1] > 0){
                p = t[p].s[0];
                while(t[p].s[0]){
                    p = t[p].s[0];
                }
                ans = p;
            }
            break;
        }
        if(t[p].val < val && t[p].val < t[ans].val){
            ans = p;
        }
        p = val < t[p].val ? t[p].s[0] : t[p].s[1];
    }
    return ans;
}

void Remove(int &p, int val){
    if(p == 0){
        return;
    }
    if(t[p].val == val){
        if(t[p].cnt > 1){
            t[p].cnt--;
            Update(p);
            return;
        }
        if(t[p].s[0] || t[p].s[1]){
            if(t[p].s[1] == 0 || t[t[p].s[0]].dat > t[t[p].s[1]].dat){
                zig(p);
                Remove(t[p].s[1],val);
            }
            else{
                zag(p);
                Remove(t[p].s[0],val);
            }
            Update(p);
        }
        else p = 0;
        return;
    }
    val < t[p].val ? Remove(t[p].s[0],val) : Remove(t[p].s[1],val);
    Update(p);
}

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    Build();
    cin>>n;
    while(n--){
        int opt,x;
        cin>>opt>>x;
        switch(opt){
            case 1:
                Insert(root,x);
                break;
            case 2:
                Remove(root,x);
                break;
            case 3:
                cout<< GetRankByVal(root,x) - 1<<endl;
                break;
            case 4:
                cout<< GetValByRank(root,x + 1)<<endl;
                break;
            case 5:
                cout<< GetPre(x)<<endl;
                break;
            case 6:
                cout<< GetNext(x)<<endl;
                break;
        }
    }
}