rt,splay查排名挂了,马蜂就这样将就着看吧
/* --------------------- pretreatment --------------------- */
#include<bits/stdc++.h>
using namespace std;
void solve();
signed main(){solve();return 0;}
// #define YNQ
#define def
#define debug
#ifdef YNQ
#define puy puts("Yes");
#define pun puts("No");
#endif
#ifdef def
#define int long long
#define V_(T) vector<T>
#define pii pair<int,int>
#define P_(T1,T2) pair<T1,T2>
#endif
static const int N=1000000;
static const int INF=0x7fffffffffffffff;
/* --------------------- library --------------------- */
namespace Splay{
struct dat{
int cnt;
int val;
};
struct Node{
int to[2];
int Fr;
int sz;
dat Vl;
void New(int fro,int vl_){
to[0]=to[1]=0;
Fr=fro;
sz=Vl.cnt=1;
Vl.val=vl_;
}
};
class Tree{
private:
V_(Node) T;
int Root;
int cnt_node;
inline void push_up(int rt)
{
T[rt].sz=T[T[rt].to[0]].sz+T[T[rt].to[1]].sz+T[rt].Vl.cnt;
}
inline void rotate(int rt)
{
int frt=T[rt].Fr;
int mairt=T[frt].Fr;
int isrt=(T[frt] .to[1]==rt);
int isfrt=(T[mairt].to[1]==frt);
T[frt].to[isrt]=T[rt].to[isrt^1];
T[T[rt].to[isrt^1]].Fr=frt;
T[rt].to[isrt^1]=frt;
T[frt].Fr=rt;
T[mairt].to[isfrt]=rt;
T[rt].Fr=mairt;
push_up(frt);
push_up(rt);
}
inline void splay(int rt,int trgt)
{
while(T[rt].Fr!=trgt){
int frt=T[rt].Fr;
int ffrt=T[frt].Fr;
if(ffrt!=trgt){
(T[frt].to[0]==rt)^(T[ffrt].to[0]==frt)?rotate(rt):rotate(frt);
}
rotate(rt);
}
if(!trgt) Root=rt;
}
public:
void find(int what)
{
int rt=Root;
while(T[rt].to[what>T[rt].Vl.val]&&what!=T[rt].Vl.val){
rt=T[rt].to[what>T[rt].Vl.val];
}
splay(rt,0);
}
int gt_pre(int what)
{
find(what);
int rt=Root;
if(what>T[rt].Vl.val){
return rt;
}
rt=T[rt].to[0];
while(T[rt].to[1]){
rt=T[rt].to[1];
}
return rt;
}
int gt_suc(int what)
{
find(what);
int rt=Root;
if(what<T[rt].Vl.val){
return rt;
}
rt=T[rt].to[1];
while(T[rt].to[0]){
rt=T[rt].to[0];
}
return rt;
}
int gt_pre_vl(int what)
{
return T[gt_pre(what)].Vl.val;
}
int gt_suc_vl(int what)
{
return T[gt_suc(what)].Vl.val;
}
void Delete(int what)
{
int pre=gt_pre(what);
int suc=gt_suc(what);
splay(pre,0);
splay(suc,pre);
int Del=T[suc].to[0];
if(T[Del].Vl.cnt>1){
T[Del].Vl.cnt--;
splay(Del,0);
}
else{
T[suc].to[0]=0;
splay(suc,0);
}
}
int gt_rank(int what)
{
find(what);
return T[T[Root].to[0]].sz;
}
int gt_val(int where)
{
int rt=Root;
while(true){
int ls=T[rt].to[0];
if(T[ls].sz+T[rt].Vl.cnt<where){
where-=T[ls].sz+T[rt].Vl.cnt;
rt=T[rt].to[1];
}
else{
if(T[ls].sz>=where){
rt=T[rt].to[0];
}
else{
break;
}
}
}
splay(rt,0);
return T[rt].Vl.val;
}
void insert(int what){
int rt=Root;
int p=0;
while(rt&&T[rt].Vl.val!=what){
p=rt;
rt=T[rt].to[what>T[rt].Vl.val];
}
if(rt){T[rt].Vl.cnt++;}
else{
rt=++cnt_node;
T[p].to[what>T[rt].Vl.val]=rt;
T[rt].New(p,what);
}
splay(rt,0);
}
Tree(int _n__=N)
{
T=V_(Node) (_n__);
insert(-1000000000);
insert(1000000000);
}
~Tree(){}
#ifdef debug
void print()
{
cout<<"\n---------\n"<<cnt_node<<'\n';
}
#endif
};
}
/* --------------------- work --------------------- */
Splay::Tree T;
void solve(){
int n;
cin>>n;
while(n--){
int opt,x;
cin>>opt>>x;
switch (opt)
{
case 1:
T.insert(x);
break;
case 2:
T.Delete(x);
break;
case 3:
cout<<T.gt_rank(x)<<'\n';
break;
case 4:
cout<<T.gt_val(x+1)<<'\n';
break;
case 5:
cout<<T.gt_pre_vl(x)<<'\n';
break;
case 6:
cout<<T.gt_suc_vl(x)<<'\n';
break;
}
}
}
‵‵‵cpp