【求助】Splay求调
  • 板块学术版
  • 楼主2020kanade
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/11/30 18:22
  • 上次更新2023/11/3 23:13:01
查看原帖
【求助】Splay求调
456724
2020kanade楼主2021/11/30 18:22

RE,目前发现kth操作会导致这一情况,其他的暂时没发现......

估计太久没写指针了,一时半会儿看不出来......

码放在下面了,提前感谢各位协助调教的神犇

#include<bits/stdc++.h>
#define nlp nullptr
#define TNP pair<node*,node*>
using namespace std;
typedef long long LL;
struct node
{
    LL v,sz,cnt,maxs;
    node* ch[2];node* fa;
    node(LL v):v(v) {ch[0]=ch[1]=nlp;sz=1,cnt=1;fa=nlp;}
    inline void up(){sz=(ch[0]?ch[0]->sz:0)+(ch[1]?ch[1]->sz:0)+cnt;maxs=(ch[0]!=nlp)?(ch[1]!=nlp?max(ch[0]->v,ch[1]->v):ch[0]->v):(ch[1]!=nlp?ch[1]->v:maxs);
    if(ch[0])ch[0]->fa=this;if(ch[1])ch[1]->fa=this;}
    inline bool get() {return this==fa->ch[1];}      
};
struct Splay
{
    node* root=nullptr;
    inline void rotate(node* &rt)
    {
        node* f=rt->fa;node* ff=(f==nullptr)?nullptr:f->fa;LL chk=rt->get();
        f->ch[chk]=rt->ch[chk^1];f->ch[chk]->fa=f;
        rt->ch[chk^1]=f;f->fa=rt;rt->fa=ff;
        if(ff) ff->ch[ff->ch[1]==f]=rt;
        f->up();rt->up();
    }
    inline void splay(node* &rhs)
    {
        for(node* f=rhs->fa;f=rhs->fa;rotate(rhs)) if(f->fa) rotate(rhs->get()==f->get()?f:rhs);
		root=rhs;
    }
    inline void splay_v(LL k)
    {
        node *rs=root;if(rs=nullptr) return;
        while(rs->v!=k && (rs->ch[k>rs->v])!=nlp) rs=rs->ch[k>rs->v];
        splay(rs);
    }
    inline void insert(LL k)
    {
        node ne(k);
        if(root==nullptr) {root= &(ne);root->up();return;}
        node* rs=root,*f=nullptr;
        while(1)
        {
            if(rs->v==k){(rs->cnt)++;rs->up();if(f) f->up();splay(rs);return;}
            f=rs;rs=rs->ch[rs->v<k];
            if(!rs){rs= &(ne);rs->fa=f;f->ch[f->v<k]=rs;rs->up();if(f) f->up();splay(rs);break;}
        }
    }
    inline LL rk(LL k)
    {
        LL ans=0;node *rs=root;
        while(1)
        {
            if(k<rs->v) rs=rs->ch[0];
            else 
            {
                ans+=(rs->ch[0]->sz);
                if(k==rs->v) {splay(rs);return ans+1;}
                ans+=rs->cnt;rs=rs->ch[1];
            }
        }
    }
    inline LL kth(LL k)
    {
        node* rs=root;
        while(1)
        {
        	cout<<"cao"<<endl;
            if(rs->ch[0]) if(k<=rs->ch[0]->sz) rs=rs->ch[0];
            else
            {
                k-=rs->cnt+rs->ch[0]->sz;
                if(k<=0) {splay(rs);return rs->v;}
                rs=rs->ch[1];
            }
        }
    }
    inline TNP split(node* &rs,LL k)
    {
        kth(k);TNP s;s.first=root;s.second=root->ch[1];root->ch[1]=nlp;s.first->up();return s;
    }
    inline node* merge(node* &rsa,node* &rsb)
    {
        if(rsa==nlp && rsb==nlp) return nullptr;
        if(rsa==nlp) return rsb;if(rsb==nlp) return rsa;
        splay_v(rsa->maxs);rsa->ch[1]=rsb;rsb->fa=rsa;return rsa;
    }
    inline void del(LL k)
    {
        rk(k);
        if((root->cnt)>1) {root->cnt--;return;}
        else root=merge(root->ch[0],root->ch[1]);return;
    }
    inline LL pre(LL k)
    {
        node *rs=root;if(!rs) return k;
        insert(k);
        while(rs->ch[1]) rs=rs->ch[1];
        splay(rs);LL ans=rs->v;del(k);return ans;
        
    }
    inline LL nxt(LL k)
    {
        node *rs=root;if(!rs) return k;
        insert(k);
        while(rs->ch[0]) rs=rs->ch[0];
        splay(rs);LL ans=rs->v;del(k);return ans;
    }
};
Splay t;LL n,op;
int main()
{
    cin>>n;
	for(auto i=1;i<=n;i++)
	{
		cin>>op;
		if(op==1){LL in;cin>>in;t.insert(in);}
		else if(op==2){LL in;cin>>in;t.del(in);}
		else if(op==3){LL in;cin>>in;cout/*<<"Step:"<<i<<" "*/<<t.rk(in)<<endl;}
		else if(op==4){LL in;cin>>in;cout/*<<"Step:"<<i<<" "*/<<t.kth(in)<<endl;}
		else if(op==5){LL in;cin>>in;cout/*<<"Step:"<<i<<" "*/<<t.pre(in)<<endl;}
		else if(op==6){LL in;cin>>in;cout/*<<"Step:"<<i<<" "*/<<t.nxt(in)<<endl;}
	}
	return 0;
}
2021/11/30 18:22
加载中...