求后继会WA,求调
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5+5;
struct node {
int l , r ;
int val , key ;
int size ;
}fhq[N] ;
int cnt , root , n ;
#include <ctime>
#include <cstdlib>
inline int newnode (int val) {
srand(time(0)) ;
fhq[++cnt].val = val ;
fhq[cnt].key = rand () ;
fhq[cnt].size = 1 ;
return cnt ;
}//建立新节点
inline void update (int now) {
fhq[now].size = fhq[fhq[now].l].size
+fhq[fhq[now].r].size+1 ;
}//更新大小
inline void split(int now,int val,int &x,int &y) { //x,y返回两棵树的根
if(!now) x = y = 0 ;
else {
if(val>=fhq[now].val) {
x = now ;
split(fhq[now].r,val,fhq[now].r,y) ;
}
else {
y = now ;
split(fhq[now].l,val,x,fhq[now].l) ;
}
update(now) ;
}
}//分裂
inline int merge(int x,int y) { //严格保证x树所有值<y树所有值
if(!x||!y) return x + y ;
if(fhq[x].key>fhq[y].key) { // > >= < <= 皆可
fhq[x].r = merge(fhq[x].r,y) ;
update(x) ;
return x ;
}
else {
fhq[y].l = merge(fhq[y].l,x) ;
update(y) ;
return y ;
}
}
int x , y , z ;
inline void ins ( int val ) {
split(root,val,x,y) ;
root = merge(merge(x,newnode(val)),y) ;
}//新建
inline void del ( int val ) {
split(root,val,x,z) ;
split(x,val-1,x,y) ;
y = merge(fhq[y].l,fhq[y].r) ;
root = merge(merge(x,y),z) ;
}//删除
inline void getrank(int val) {
split(root,val-1,x,y) ;
cout << fhq[x].size + 1 << endl ;
root = merge(x,y) ;
}
inline void getnum(int rank) {
int now = root ;
while(now) {
if(fhq[fhq[now].l].size+1==rank) {
break;
}
else if(fhq[fhq[now].l].size>=rank) {
now = fhq[now].l ;
}
else {
rank-=fhq[fhq[now].l].size + 1 ;
now = fhq[now].r ;
}
}
cout << fhq[now].val << endl ;
}
inline void pre(int val) {
split(root,val-1,x,y) ;
int now = x ;
while(fhq[now].r)
now = fhq[now].r;
cout << fhq[now].val << endl ;
root = merge(x,y) ;
}
inline void nxt(int val) {
split(root,val,x,y) ;
int now = y ;
while(fhq[now].l)
now = fhq[now].l;
cout << fhq[now].val << endl ;
root = merge(x,y) ;
}
int main ( ) {
cin >> n ;
while(n--) {
int opt , x ;
cin >> opt >> x ;
switch(opt) {
case 1 :
ins(x) ;
break ;
case 2 :
del(x) ;
break ;
case 3 :
getrank(x) ;
break ;
case 4 :
getnum(x) ;
break ;
case 5 :
pre(x) ;
break ;
case 6 :
nxt(x) ;
break ;
}
}
// system("pause") ;
return 0 ;
}