splay模板 指针版&splay被卡祭

普通平衡树板子

访问空指针会出错，我用了一个nil代替他。（c++是谁设计的我还得把结构体定义在外面真难受）

#include
using namespace std;
#define forg(i,x) for(rint i=fir[x];i;i=nxt[i])
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define rint register int
#define uu unsigned
#define scanf a1234=scanf
int a1234;
typedef long long ll;
typedef uu long long ull;
typedef pair pii;
inline void xxx(){for(;;);}
inline int rd(int l,int r){return rand()%(r-l+1)+l;}

int n;
struct node{
    node*ch[2],*prt;
    int siz,cnt,val;
    inline void up(){siz=ch[0]->siz+ch[1]->siz+cnt;}
}*nil;
class P{
    public:
    node*rt;
    inline void init(){
        nil=new node;nil->ch[0]=nil->ch[1]=nil->prt=nil;
        nil->cnt=nil->siz=0;
        rt=nil;
    }
    inline void rotate(node*x){
        node*f=x->prt,*g=f->prt;
        int k=son(x),kk=son(f);
        conn(x->ch[k^1],f,k),conn(f,x,k^1);
        f->up(),x->up();
        if(g==nil)rt=x,rt->prt=nil;
        else conn(x,g,kk);
    }
/*
    inline void dfs(node*x){
        assert(nil->siz==0&&nil->cnt==0&&nil->ch[0]==nil&&nil->ch[1]==nil);assert(nil->prt==nil);
        if(x->ch[0]!=nil)assert(x->ch[0]->valval),dfs(x->ch[0]);
        if(x->ch[1]!=nil)assert(x->ch[1]->val>x->val),dfs(x->ch[1]);
    }*/
    inline void conn(node*x,node*f,int k){f->ch[k]=x;if(x!=nil)x->prt=f;}
    inline bool son(node*x){return x==x->prt->ch[1];}
    inline void splay(node*x,node*y=nil){
        while(x->prt!=y){
            node*f=x->prt;
            if(f->prt==y)return rotate(x);
            if(son(x)^son(f))rotate(x),rotate(x);
            else rotate(f),rotate(x);
        }
    }
    inline node*find(int v){
        node*x=rt;
        while(1){
            if(x->val==v)return splay(x),x;
            x=x->ch[v>x->val];
        }
    }
    inline void ins(int v){
       if(rt==nil)return rt=newd(v),void();
        node*x=rt;
        while(1){
            ++x->siz;
            if(x->val==v)return ++x->cnt,splay(x);
            node*&nxt=x->ch[v>x->val];
            if(nxt==nil)return nxt=newd(v,x),splay(nxt);
            x=nxt;
        }
    }
    inline node*newd(int v,node*f=nil){
        node*x=new node(*nil);
        x->prt=f,x->val=v,x->siz=x->cnt=1;
        return x;
    }
    inline void era(int v){
        find(v);
        --rt->siz;
        if(--rt->cnt==0){
            node*x;
            if(rt->ch[0]==nil)x=rt->ch[1];
            else if(rt->ch[1]==nil)x=rt->ch[0];
            else{
                x=rt->ch[0];
                while(x->ch[1]!=nil)x=x->ch[1];
                splay(x,rt);
                conn(rt->ch[1],x,1);
            }
            delete rt;rt=x,x->up(),x->prt=nil;
        }
    }
    inline int getrk(int v){
        int res=0;
        node*x=rt,*nxt;
        while(1){
            nxt=x->ch[v>x->val];
            if(v>x->val)res+=x->ch[0]->siz+x->cnt;
            if(nxt==nil)return splay(x),res+1;
            x=nxt;
        }
    }
    inline node*kth(int k){
        assert(k>0&&k<=rt->siz);
        node*x=rt;
        while(1){
            int c=x->ch[0]->siz;
            if(k<=c)x=x->ch[0];
            else if(k<=c+x->cnt)return splay(x),x;
            else k-=c+x->cnt,x=x->ch[1];
        }
    }
    inline node*lower(int v){return kth(getrk(v)-1);}
    inline node*upper(int v){return kth(getrk(v+1));}
}sp;

int main(){
    sp.init();
    scanf("%d",&n);while(n--){
        int o,x;scanf("%d%d",&o,&x);
        switch(o){
            case 1:sp.ins(x);break;
            case 2:sp.era(x);break;
            case 3:printf("%d\n",sp.getrk(x));break;
            case 4:printf("%d\n",sp.kth(x)->val);break;
            case 5:printf("%d\n",sp.lower(x)->val);break;
            case 6:printf("%d\n",sp.upper(x)->val);break;
        }
    }
    return 0;
}

原来的splay被卡了

据我观察，这组数据很多人都跑不过去，你要不要也试试呢，嘿嘿

其实splay就是一个splay操作而已 可你甚至连它都用不对

为你奉上一份数据生成器

#include
using namespace std;
typedef pair pii;
#define forg(i,x) for(int i=first[x];i;i=nxt[i])
#define uu unsigned
#define fi first
#define se second
#define od(x) ((x)&1)
#define ev(x) (od(x)^1)
#define mi2(x) (1<<(x))
#define scanf a1234=scanf
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
int a1234;
char buf[1<<18],*bufs=buf,*buft=buf;
inline int gc(){
    return bufs==buft&&(buft=(bufs=buf)+fread(buf,1,1<<18,stdin)),bufs==buft?-1:*bufs++;
}
inline void xxx(){for(;;);}

inline int rd(int l,int r){return rand()%(r-l+1)+l;}
int n=5e4;
inline void work(){
    printf("%d\n",n*2);
    for(int i=1;i<=n;++i)printf("1 %d\n",i*2);
    for(int i=1;i<=n;++i)printf("5 %d\n",od(rand())?3:2*n+1);
}
int main(){
    srand((uu)time(0));
    work();
    return 0;
}

为什么把有些splay删掉以后跑的比fhqtreap还快。。