splay的一些事情

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

逆天峰王者 @ 2020-05-02 08:13:35

请问这种写法的splay不加入边界INF和-INF,就会又wrong,又T,请问大佬原因?
刚学splay,希望大佬指点!在此谢过!

#include<bits/stdc++.h>
#define db double
#define RE register
#define ll long long
#define P 1000000007
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define pb(x) push_back(x)
#define ull unsigned long long
#define put(x) printf("%d\n",x)
#define getc(a) scanf("%s",a+1)
#define putl(x) printf("%lld\n",x)
#define rep(i,x,y) for(RE int i=x;i<=y;++i)
#define fep(i,x,y) for(RE int i=x;i>=y;--i)
#define go(x) for(int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=2e6+10;
int n,m,last,root,tot,ans;
struct wy
{
    int v,f,ch[2],sum,rec;
    #define v(x) t[x].v
    #define f(x) t[x].f
    #define sum(x) t[x].sum
    #define rec(x) t[x].rec
    #define ch(x,y) t[x].ch[y]
}t[N];
inline int read()
{
    int x=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*ff;
}

inline void updata(int x) {sum(x)=sum(ch(x,0))+sum(ch(x,1))+rec(x);}

inline int random(int n){return (ll)rand()*rand()%n;}

inline void retato(int x)
{
    int y=f(x),z=f(y),k=ch(y,1)==x;
    ch(z,ch(z,1)==y)=x;f(x)=z;
    ch(y,k)=ch(x,k^1);f(ch(x,k^1))=y;
    ch(x,k^1)=y;f(y)=x; 
    updata(y);updata(x);
}

inline void splay(int x,int goal)
{
    while(f(x)!=goal)
    {
        int y=f(x),z=f(y);
        if(z!=goal) (ch(z,0)==y)^(ch(y,0)==x)?retato(x):retato(y);
        retato(x);
    }   
    if(goal==0) root=x;
}

inline int newpoint(int x,int fa)
{
    f(++tot)=fa;v(tot)=x;sum(tot)=rec(tot)=1;
    return tot; 
}

inline void insert(int x)
{
    int now=root;
    if(!now) {root=newpoint(x,0);return;}   
    while(1)
    {
        sum(now)++;
        if(v(now)==x) {rec(now)++;splay(now,0);return;}
        int next=x>v(now);
        if(!ch(now,next))
        {
            int p=newpoint(x,now);
            ch(now,next)=p;
            splay(p,0);return;
        }
        now=ch(now,next);
    }
}

inline void find(int x)
{
    int now=root;
    if(!now) return;
    while(v(now)!=x&&ch(now,x>v(now))) now=ch(now,x>v(now));
    splay(now,0);
}

inline int Next(int x,int op)
{
    find(x);
    int now=root;
    if(v(now)>x&&op) return now;
    if(v(now)<x&&!op) return now;
    now=ch(now,op);
    while(ch(now,op^1)) now=ch(now,op^1);
    return now;
} 

inline void delet(int x)
{
    int last=Next(x,0),next=Next(x,1);
    splay(last,0);splay(next,last);
    int now=ch(next,0);
    if(rec(now)>1) rec(now)--,splay(now,0);
    else ch(next,0)=0;
} 

inline int Kth(int x)
{
    int now=root;
    while(1)
    {
        int y=ch(now,0);
        if(x>sum(y)+rec(now)) 
        {
            x-=sum(y)+rec(now);
            now=ch(now,1);
        }
        else if(sum(y)>=x) now=ch(now,0);
        else
        {
            splay(now,0);
            return v(now);
        }
    }
}

int main()
{
    //freopen("1.in","r",stdin);
    get(n);get(m);
    insert(INF*2);insert(-INF*2);
    rep(i,1,n) 
    {
        int get(x);
        insert(x);
    }
    rep(i,1,m)
    {
        int get(opt),get(x);
        x^=last;
        if(opt==1) insert(x);
        else if(opt==2) delet(x);   
        else if(opt==3)
        {
            find(x);
            last=sum(ch(root,0));
            if(v(root)<x) last+=rec(root);
            ans^=last;
        }
        else if(opt==4) last=Kth(x+1),ans^=last; 
        else if(opt==5) last=v(Next(x,0)),ans^=last;
        else if(opt==6) last=v(Next(x,1)),ans^=last;
    }
    put(ans);
    return 0;
}

by Flandre_495 @ 2020-05-02 08:24:06

不加边界的话在删除元素时有可能找不到后继或前驱


by 逆天峰王者 @ 2020-05-02 09:07:29

@Flandre_495
所以问题出在前驱,后继,与删除上了吗??
其他的操作应该没问题吧?


by Flandre_495 @ 2020-05-02 10:01:33

@逆天峰王者 大概吧?


by 逆天峰王者 @ 2020-05-02 10:51:31

@Flandre_495 谢啦,我再调试会.!


by 逆天峰王者 @ 2020-05-02 23:01:41

//不等,不问,不犹豫,不回头.
#include<bits/stdc++.h>
#define _ 0
#define db double
#define RE register
#define ll long long
#define P 1000000007
#define INF 2000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define pb(x) push_back(x)
#define ull unsigned long long
#define put(x) printf("%d\n",x)
#define getc(a) scanf("%s",a+1)
#define putl(x) printf("%lld\n",x)
#define rep(i,x,y) for(RE int i=x;i<=y;++i)
#define fep(i,x,y) for(RE int i=x;i>=y;--i)
#define go(x) for(int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=1e6+10;
int tot,n,m,root,last,ans;
struct wy
{
    int ch[2],v,f,sum,rec;
    #define ch(x,y) t[x].ch[y]
    #define sum(x) t[x].sum
    #define rec(x) t[x].rec
    #define v(x) t[x].v
    #define f(x) t[x].f
}t[N];

inline int read()
{
    int x=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*ff;
}

inline void updata(int x){sum(x)=sum(ch(x,0))+sum(ch(x,1))+rec(x);} 

inline void retate(int x)
{
    int y=f(x),z=f(y),k=ch(y,1)==x; 
    ch(z,ch(z,1)==y)=x;f(x)=z;
    ch(y,k)=ch(x,k^1);f(ch(x,k^1))=y;
    ch(x,k^1)=y;f(y)=x; 
    updata(y);updata(x);
}

inline void splay(int x,int goal)
{
    while(f(x)!=goal)
    {
        int y=f(x),z=f(y);
        if(z!=goal) (ch(z,0)==y)^(ch(y,0)==x)?retate(x):retate(y);
        retate(x);
    }
    if(goal==0) root=x;
}

inline void find(int x)
{
    int now=root;
    if(!now) return;
    while(1)
    {
        if(!now) return;
        if(v(now)==x) {splay(now,0);return;}
        int next=x>v(now);
        now=ch(now,next);
    }
}

inline int newpoint(int x,int fa)
{
    v(++tot)=x;f(tot)=fa;rec(tot)=sum(tot)=1;
    return tot; 
}

inline void insert(int x)
{
    int now=root;
    if(!now) {root=newpoint(x,0);return;}
    while(1)
    {
        sum(now)++;
        if(v(now)==x) {rec(now)++;splay(now,0);return;}
        int next=x>v(now);
        if(!ch(now,next)) 
        {
            int p=newpoint(x,now);
            ch(now,next)=p;
            splay(p,0);return;
        }
        now=ch(now,next); 
    }
}

inline void delet(int x)
{
    find(x);
    int now=root;
    if(rec(now)>1) {rec(now)--;sum(now)--;return;}
    else if(!ch(now,0)&&!ch(now,1)) {root=0;return;}
    else if(!ch(now,0)) {root=ch(now,1);f(ch(now,1))=0;return;}
    else 
    {
        int left=ch(now,0);
        while(ch(left,1)) left=ch(left,1);
        splay(left,now);
        ch(left,1)=ch(now,1);f(ch(now,1))=left;
        f(left)=0;root=left;
        updata(left);
    }
}

inline int rank(int x)
{
    int now=root,ans=0;
    while(1)
    {
        if(!now) return ans+1;
        if(v(now)==x) return ans+sum(ch(now,0))+1;
        int next=x>v(now);
        if(next) ans+=sum(ch(now,0))+rec(now);
        now=ch(now,next);
    }
}

inline int kth(int x)
{
    int now=root;
    while(1)
    {
        int y=ch(now,0);
        if(x>sum(y)+rec(now))
        {
            x-=sum(y)+rec(now);
            now=ch(now,1);
        }
        else if(sum(y)>=x) now=ch(now,0);
        else return v(now);
    }
}

inline int lower(int x)
{
    int now=root,ans=-INF;
    while(1)
    {
        if(!now) return ans;
        if(v(now)<x) ans=max(ans,v(now));
        int next=x<=v(now)?0:1;
        now=ch(now,next);
    }
}

inline int next(int x)
{
    int now=root,ans=INF;
    while(1)
    {
        if(!now) return ans;
        if(v(now)>x) ans=min(ans,v(now));
        int next=x>v(now);
        now=ch(now,next);
    }
}

int main()
{
//  freopen("1.in","r",stdin);
    get(n);get(m);
    rep(i,1,n)
    {
        int get(x);
        insert(x);
    }
    rep(i,1,m)
    {
        int get(op),get(x);
        x^=last;
        if(op==1) insert(x);
        else if(op==2) delet(x);
        else if(op==3) ans^=(last=rank(x));
        else if(op==4) ans^=(last=kth(x));
        else if(op==5) ans^=(last=lower(x));
        else if(op==6) ans^=(last=next(x)); 
    }
    put(ans);
    return 0;
}
//以吾之血,祭吾最后的亡魂

@Flandre_495 这是修改后的,将前驱后继删除都变了,可还是有问题啊??劳烦大佬了...


|