#include<iostream>
#define MAXN 100010
using namespace std;
int n , root , cnt , opt , x;
struct node{
int left , right , size , value , num ;
node(int l , int r , int s , int v)
: left(l),right(r),size(s),value(v),num( 1 ) {}
node() {}
}t[MAXN];
inline void update(int root){
t[root].size = t[t[root].left].size + t[t[root].right].size +t[root].num;
}
int rank(int x , int root){
if( root )
{
if(x < t[root].value)
return rank(x , t[root].left);
if(x > t[root].value)
return rank(x , t[root].right) +t[t[root].left].size +t[root].num;
return t[ t[ root ].left ].size + t[root].num;
}
return 1;
}
int kth(int x,int root){
if(x <= t[t[root].left].size)
return kth(x,t[root].left);
if(x <= t[t[root].left].size + t[root].num)
return t[root].value;
return kth(x - t[t[root].left].size - t[root].num , t[root].right);
}
void insert(int x , int & root){
if(x < t[root].value)
if(!t[root].left)
t[t[root].left = ++cnt] = node(0,0,1,x);
else
insert(x,t[root].left);
else if(x > t[root].value)
if(!t[root].right)
t[t[root].right = ++cnt] = node(0,0,1,x);
else
insert(x,t[root].right);
else
t[root].num++;
update(root);
}
int main() {
cin>>n;
int num = 0;
t[root = ++cnt] = node(0 ,0 , 1 , 2147483647);
while(n--){
cin>>opt>>x;
num++;
if(opt == 1) cout<<rank(x , root)<<endl;
else if(opt == 2) cout<<kth(x , root)<<endl;
else if(opt == 3) cout<<kth(rank(x , root) - 1 , root)<<endl;
else if(opt == 4) cout<<kth(rank(x + 1 , root) , root)<<endl;
else num-- , insert(x,root);
}
return 0;
}
本地样例愉快地过了,但是在洛谷评测时冷不丁冒出来一句: “对RANK的引用有歧义”
哪位大佬帮我看看错误点?