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;
}