照着深基打的,为啥输入三个数就没任何反应了?我买了一本假的?
#include<bits/stdc++.h>
#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(1),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].left = ++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++;
switch(opt){
case 1: cout<< rank(x,root) << endl;
case 2: cout<< kth(x,root) << endl;
case 3: cout<< kth(rank(x,root) - 1,root) << endl;
case 4: cout<< kth(rank(x + 1,root),root) << endl;
default: num--,insert(x,root);
}
}
return 0;
}