小样例本蒟蒻的程序输出2335,结果过了?
#include<bits/stdc++.h>
using namespace std;
int n,opt,x;
const int N=500005;
int total=0;
struct node{
int val,cnt,siz,l,r;//siz为子树的节点数,cnt为记重复的权值结点
}tree[N];
void add(int x,int v){
tree[x].siz++;
if(tree[x].val==v){
tree[x].cnt++;
return;
}
if(v<tree[x].val){
if(tree[x].l!=0){
add(tree[x].l,v);
}
else{
total++;
tree[total].val=v;
tree[total].siz=tree[total].cnt=1;
tree[x].l=total;
}
}
else{
if(tree[x].r!=0){
add(tree[x].r,v);
}
else{
total++;
tree[total].val=v;
tree[total].siz=tree[total].cnt=1;
tree[x].r=total;
}
}
}
int find_precursor(int x,int v,int ans){
if(tree[x].val>v){
if(tree[x].l==0){
return ans;
}
else{
return find_precursor(tree[x].l,v,ans);
}
}
else{
if(tree[x].r==0){
return tree[x].val<v?tree[x].val:ans;
}
if(tree[x].cnt!=0){
return find_precursor(tree[x].r,v,tree[x].val);
}
else{
return find_precursor(tree[x].r,v,ans);
}
}
}
int find_successor(int x,int v,int ans){
if(tree[x].val<=v){
if(tree[x].r==0){
return ans;
}
else{
return find_successor(tree[x].r,v,ans);
}
}
else{
if(tree[x].l==0){
return tree[x].val>v?tree[x].val:ans;
}
if(tree[x].cnt!=0){
return find_successor(tree[x].l,v,tree[x].val);
}
else{
return find_successor(tree[x].l,v,ans);
}
}
}
int find_ranking(int x,int v){
if(x==0){
return 0;
}
if(v==tree[x].val){
return tree[tree[x].l].siz;
}
else if(v<tree[x].val){
return find_ranking(tree[x].l,v);
}
else{
return find_ranking(tree[x].r,v)+tree[tree[x].l].siz+tree[x].cnt;
}
}
int ranking_find(int x,int rk){
if(x==0){
return 2147483647;
}
if(tree[tree[x].l].siz>=rk){
return ranking_find(tree[x].l,rk);
}
if(tree[tree[x].l].siz+tree[x].cnt>=rk){
return tree[x].val;
}
return ranking_find(tree[x].r,rk-tree[tree[x].l].siz-tree[x].cnt);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d",&opt,&x);
if(opt==1){
printf("%d\n",find_ranking(1,x)+1);
}
else if(opt==2){
printf("%d\n",ranking_find(1,x));
}
else if(opt==3){
printf("%d\n",find_precursor(1,x,-2147483647));
}
else if(opt==4){
printf("%d\n",find_successor(1,x,2147483647));
}
else{
if(total==0){
total++;
tree[total].cnt=tree[total].siz=1;
tree[total].val=x;
}
else{
add(1,x);
}
}
}
return 0;
}
求大佬解惑