0分求条
查看原帖
0分求条
921417
crean_楼主2024/3/12 19:38

很奇怪,开O2就TLE, 不开就MLE

#include<bits/stdc++.h>
using namespace std;
const int INF=0x7fffffff;
struct Tree{
	int data,lchild,quan,rchild,sum;//数据,左节点位置,这个数出现次数,右孩子位置 ,子树大小 
}tree[10005];
int n,pl=1;
void csh(int x,int y){
	tree[x].data=y; 
	tree[x].quan=1;
	tree[x].sum=1;
	return;
}
void insert(int x,int po){
	tree[po].sum++;
	if(pl==1){
		csh(po,x);
		pl++;
		return ;
	}
	if(x==tree[po].data){
		tree[po].quan++;
		return ;
	} 
	else if(x<tree[po].data){
		if(tree[po].lchild==0){
			tree[po].lchild=pl; 
			csh(pl,x);
			pl++;
			return;
		}
		else{
			insert(x,tree[po].lchild);
		}
	}
	else if(x>tree[po].data){
		if(tree[po].rchild==0){
			tree[po].rchild=pl; 
			csh(pl,x);
			pl++;
			return;
		}
		else{
			insert(x,tree[po].rchild);
		}
	}
	return;
}
int rank1(int x,int po){
	if(x==0) return 0; 
	if(tree[po].data==x) return tree[tree[po].lchild].sum;
	else if(x>tree[po].data){
		return tree[po].sum-tree[tree[po].rchild].sum+rank1(x,tree[po].rchild);
	}
	else if(x<tree[po].data){
		return rank1(x,tree[po].rchild);
	}
}
int rrank1(int x,int po){
	if(po==0) return INF;
	else if(x<=tree[tree[po].lchild].sum) return rrank1(x,tree[po].lchild );
	else if(x<=tree[tree[po].lchild].sum+tree[po].quan) return tree[po].data;
	return rrank1(x-tree[tree[po].lchild].sum-tree[po].quan,tree[po].rchild);
}
int fd(int x,int po,int ans){
	if(x<=tree[po].data){
		if(tree[po].lchild==0) return ans;
		return fd(x,tree[po].lchild,ans);
	}
	else if(x>tree[po].data){
		if(tree[po].rchild==0) return tree[po].data;
		else return fd(x,tree[po].rchild,tree[po].data);
	}
}
int bd(int x,int po,int ans){
	if(x>=tree[po].data){
		if(tree[po].rchild==0) return ans;
		return bd(x,tree[po].rchild,ans);
	}
	else if(x<tree[po].data){
		if(tree[po].lchild==0) return tree[po].data;
		else return bd(x,tree[po].lchild,tree[po].data);
	}
}
int main(){
	//ios::sync_with_stdio(false);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int op,t;
		scanf("%d%d",&op,&t);
		if(op==1) printf("%d\n",rank1(t,1)+1);
		else if(op==2) printf("%d\n",rrank1(t,1));
		else if(op==3) printf("%d\n",fd(t,1,-2147483647));
		else if(op==4) printf("%d\n",bd(t,1,2147483647));
		else if(op==5) insert(t,1); 
	}
	return 0;
}

按照题解调了三个小时了

2024/3/12 19:38
加载中...