我怕不是写了一个假的Splay

P6136 【模板】普通平衡树(数据加强版)

7KByte @ 2020-03-03 22:32:34

为啥别人的Splay少说50分多的80/90分,我的MLE30?/kel

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define N 1000005
#define M 100005
using namespace std;
int n,m,u[M],b[N],c[N];
struct node{
    int val,sz,fa,son[2],cnt;
}a[N+M];
#define ls a[x].son[0]
#define rs a[x].son[1]
#define F a[x].fa
void link(int x,int y,int which){
    a[x].fa=y;a[y].son[which]=x;
}
void updata(int x){
    a[x].sz=a[ls].sz+a[rs].sz+a[x].cnt;
}
int son(int x){
    return a[F].son[1]==x;
}
#define rt a[0].son[1]
void rotate(int x){
    int y=F;
    int f=a[y].fa;
    int whichx=son(x);
    int whichy=son(y);
    link(a[x].son[whichx^1],y,whichx);
    link(y,x,whichx^1);link(x,f,whichy);
    updata(y);updata(x);
}
void splay(int x,int to){
    int nd=a[to].fa;
    while(F^nd){
        if(a[F].fa==nd)rotate(x);
        else if(son(F)==son(x))rotate(F),rotate(x);
        else rotate(x),rotate(x);
    }
}
int tot = 0;
int New(int val){
    ++tot;
    a[tot].son[0]=a[tot].son[1]=a[tot].fa=0;
    a[tot].sz=a[tot].cnt=1;a[tot].val=val;
    return tot;
}
int build(int l,int r){
    if(l>r)return 0;
    int mid=(l+r)>>1;
    int p=New(b[mid]);
    a[p].cnt=c[mid];
    link(build(l,mid-1),p,0);
    link(build(mid+1,r),p,1);
    updata(p);
    return p;
}
int rank(int x,int val){
    if(!x)return 0;
    if(a[x].val==val)return a[ls].sz;
    if(a[x].val>val)return rank(ls,val);
    return a[ls].sz+a[x].cnt+rank(rs,val);
}
int gval(int x,int rk){
    if(!x)return -1;
    if(a[ls].sz>=rk)return gval(ls,rk);
    if(a[ls].sz+a[x].cnt>=rk)return x;
    return gval(rs,rk-a[ls].sz-a[x].cnt);
}
void insert(int x,int val){
    if(a[x].val==val)a[x].cnt++;
    else if(a[x].val>val){
        if(!ls)link(New(val),x,0);
        else insert(ls,val);
    }
    else{
        if(!rs)link(New(val),x,1);
        else insert(rs,val);
    }
    updata(x);
}
int remove(int x,int val){
    if(a[x].val==val){
        if(a[x].cnt){a[x].cnt--;updata(x);return x;}
        if(!ls&&!rs)return 0;
        if(!ls){
            rotate(rs);x=F;
            link(remove(ls,val),x,0);
            updata(x);
        }
        else{
            rotate(ls);x=F;
            link(remove(rs,val),x,1);
            updata(x);
        }
    }
    else if(a[x].val>val)link(remove(ls,val),x,0);
    else link(remove(rs,val),x,1);
    updata(x);return x;
}
int gpre(int val){
    int x=rt,ans=0;
    while(x){
        if(a[x].val>=val)x=ls;
        else ans=max(ans,a[x].val),x=rs;
    }
    return ans;
}
int gnxt(int val){
    int x=rt,ans=0x7fffffff;
    while(x){
        if(a[x].val<=val)x=rs;
        else ans=min(ans,a[x].val),x=ls;
    }
    return ans;
}
void dfs(int x){
    if(!x)return;
    dfs(ls);
    rep(i,1,a[x].cnt)printf("%d ",a[x].val);
    dfs(rs);
}
int T=0,size=0;
// By Inf_Voltage
int main(){
    srand(time(0));
    //freopen("P6136_1.in","r",stdin);
    scanf("%d%d",&n,&m);
    rep(i,1,n)scanf("%d",&u[i]);
    sort(u,u+n+1);
    rep(i,0,n)if(!i||u[i]^u[i-1])b[++T]=u[i],c[T]=1;else c[T]++;
    size=n+1;
    link(build(1,T),0,1);
    //cout<<"ss"<<endl;dfs(rt);cout<<"\ntt"<<endl;
    int ans=0,pre=0;
    rep(i,1,m){
        int op,x;scanf("%d%d",&op,&x);
        x^=pre;
        //cout<<"Start : "<<op<<" "<<x<<endl;
        if(op==1)insert(rt,x),splay(tot,rt),size++;
        else if(op==2)link(remove(rt,x),0,1),size--;
        else{ 
            if(op==3)pre=rank(rt,x);
            else if(op==4)pre=gval(rt,x+1),splay(pre,rt),pre=a[pre].val;
            else if(op==5)pre=gpre(x);
            else pre=gnxt(x);
            ans^=pre;
            //cout<<pre<<endl;
        }
        //if(son(rt)!=1)puts("Error");
        //cout<<"ss"<<endl;dfs(rt);cout<<"\ntt"<<endl;
        //if(tot>1100000){puts("WA");return 0;}
        int rd=(rand()<<15)^rand();
        if(rand()%103==0)splay(gval(rt,rd%size+1),rt);
    }
    printf("%d\n",ans);
    return 0;
} 

by 万万没想到 @ 2020-03-03 22:33:35

Fhq-treap吼啊!


by hly1204 @ 2020-03-03 22:36:37

一般70-100分的splay都正常吧?


by 7KByte @ 2020-03-03 22:45:32

@hly1204 显然是我写假了,已解决


by jyttoby @ 2020-03-03 22:58:58

我也怕不是写了一个假的 Splay


|