小样例错了,结果AC了?
查看原帖
小样例错了,结果AC了?
566903
福明o7楼主2022/8/6 20:07

小样例本蒟蒻的程序输出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;
}

求大佬解惑

2022/8/6 20:07
加载中...