小清新马蜂splay模板在线求调
查看原帖
小清新马蜂splay模板在线求调
705725
P_VICVIC_R楼主2024/1/3 13:13

rt,splay查排名挂了,马蜂就这样将就着看吧

/* --------------------- pretreatment --------------------- */

#include<bits/stdc++.h>
using namespace std;
void solve();
signed main(){solve();return 0;}

// #define YNQ
#define def
#define debug

#ifdef YNQ
#define puy puts("Yes");
#define pun puts("No");
#endif
#ifdef def
#define int long long
#define V_(T) vector<T>
#define pii pair<int,int>
#define P_(T1,T2) pair<T1,T2>
#endif
static const int N=1000000; 
static const int INF=0x7fffffffffffffff; 

/* --------------------- library --------------------- */

namespace Splay{
struct dat{
    int cnt;
    int val;
};
struct Node{
    int to[2];
    int Fr;
    int sz;
    dat Vl;
    void New(int fro,int vl_){
        to[0]=to[1]=0;
        Fr=fro;
        sz=Vl.cnt=1;
        Vl.val=vl_;
    }
};
class Tree{
private:
    V_(Node) T;
    int Root;
    int cnt_node;
    inline void push_up(int rt)
{
    T[rt].sz=T[T[rt].to[0]].sz+T[T[rt].to[1]].sz+T[rt].Vl.cnt;
}
    inline void rotate(int rt)
{
    int frt=T[rt].Fr;
    int mairt=T[frt].Fr;
    int isrt=(T[frt] .to[1]==rt);
    int isfrt=(T[mairt].to[1]==frt);
    T[frt].to[isrt]=T[rt].to[isrt^1];
    T[T[rt].to[isrt^1]].Fr=frt;
    T[rt].to[isrt^1]=frt;
    T[frt].Fr=rt;
    T[mairt].to[isfrt]=rt;
    T[rt].Fr=mairt;
    push_up(frt);
    push_up(rt);
}                                                                                                
    inline void splay(int rt,int trgt)
{
    while(T[rt].Fr!=trgt){
        int frt=T[rt].Fr;
        int ffrt=T[frt].Fr;
        if(ffrt!=trgt){
            (T[frt].to[0]==rt)^(T[ffrt].to[0]==frt)?rotate(rt):rotate(frt);
        }
        rotate(rt);
    }
    if(!trgt) Root=rt;
}
public:
    void find(int what)
{
    int rt=Root;
    while(T[rt].to[what>T[rt].Vl.val]&&what!=T[rt].Vl.val){
        rt=T[rt].to[what>T[rt].Vl.val];
    }
    splay(rt,0);
}
    int gt_pre(int what)
{   
    find(what);
    int rt=Root;
    if(what>T[rt].Vl.val){
        return rt;
    }
    rt=T[rt].to[0];
    while(T[rt].to[1]){
        rt=T[rt].to[1];
    }
    return rt;
}
    int gt_suc(int what)
{
    find(what);
    int rt=Root;
    if(what<T[rt].Vl.val){
        return rt;
    }
    rt=T[rt].to[1];
    while(T[rt].to[0]){
        rt=T[rt].to[0];
    }
    return rt;
}
    int gt_pre_vl(int what)
{
    return T[gt_pre(what)].Vl.val;
}
    int gt_suc_vl(int what)
{
    return T[gt_suc(what)].Vl.val;
}
    void Delete(int what)
{
    int pre=gt_pre(what);
    int suc=gt_suc(what);
    splay(pre,0);
    splay(suc,pre);
    int Del=T[suc].to[0];
    if(T[Del].Vl.cnt>1){
        T[Del].Vl.cnt--;
        splay(Del,0);
    }
    else{
        T[suc].to[0]=0;
        splay(suc,0);
    }
}
    int gt_rank(int what)
{
    find(what);
    return T[T[Root].to[0]].sz;
}
    int gt_val(int where)
{
    int rt=Root;
    while(true){
        int ls=T[rt].to[0];
        if(T[ls].sz+T[rt].Vl.cnt<where){
            where-=T[ls].sz+T[rt].Vl.cnt;
            rt=T[rt].to[1];
        }
        else{
            if(T[ls].sz>=where){
                rt=T[rt].to[0];
            }
            else{
                break;
            }
        }
    }
    splay(rt,0);
    return T[rt].Vl.val;
}
    void insert(int what){
        int rt=Root;
        int p=0;
        while(rt&&T[rt].Vl.val!=what){
            p=rt;
            rt=T[rt].to[what>T[rt].Vl.val];
        }
        if(rt){T[rt].Vl.cnt++;}
        else{
            rt=++cnt_node;
            T[p].to[what>T[rt].Vl.val]=rt;
            T[rt].New(p,what);
        }
        splay(rt,0);
    }
    Tree(int _n__=N)
    {
        T=V_(Node) (_n__);
        insert(-1000000000);
        insert(1000000000);
    }
    ~Tree(){}
#ifdef debug
    void print()
{
    cout<<"\n---------\n"<<cnt_node<<'\n';
}
#endif 
};
}

/* --------------------- work --------------------- */

Splay::Tree T;

void solve(){
    int n;
    cin>>n;
    while(n--){
        int opt,x;
        cin>>opt>>x;
        switch (opt)
        {
        case 1:
                T.insert(x);
            break;
        case 2:
                T.Delete(x);
            break;
        case 3:
                cout<<T.gt_rank(x)<<'\n';
            break;
        case 4:
                cout<<T.gt_val(x+1)<<'\n';
            break;
        case 5:
                cout<<T.gt_pre_vl(x)<<'\n';
            break;
        case 6:
                cout<<T.gt_suc_vl(x)<<'\n';
            break;
        }        
    }
}
‵‵‵cpp
2024/1/3 13:13
加载中...