玄关,30pts RE
查看原帖
玄关,30pts RE
970132
Hero_Broom楼主2024/8/12 16:23

本地运行的时候没有RE但交上去就30pts RE了?

#include<bits/stdc++.h>
using namespace std;
struct node{
	node *l,*r;
	int val,fix,weight;
	int size,lsize,rsize;
};
void Update_Size(node*& root){
	if(root==NULL) return;
	int ans=root->weight;
	if(root->l!=NULL) ans+=root->l->size;
	if(root->r!=NULL) ans+=root->r->size;
	root->size=ans;
}
void Left_Rotate(node*& root){
	node* tmp=root->r;
	root->r=tmp->l;
	tmp->l=root;
	Update_Size(root);
	Update_Size(tmp);
	root=tmp;
}
void Right_Rotate(node*& root){
	node* tmp=root->l;
	root->l=tmp->r;
	tmp->r=root;
	Update_Size(root);
	Update_Size(tmp);
	root=tmp;
}
void Treap_Insert(node*& root,int v){
	if(root==NULL){
		root=new node();
		root->l=NULL,root->r=NULL;
		root->size=1;
		root->val=v;
		root->weight=1;
		root->fix=rand();
		return;
	}
	if(v<root->val){
		Treap_Insert(root->l,v);
		if(root->l->fix<root->fix) Right_Rotate(root);
		Update_Size(root);
	}
	else if(v>root->val){
		Treap_Insert(root->r,v);
		if(root->r->fix<root->fix) Left_Rotate(root);
		Update_Size(root);
	}else{
		root->size++;
		root->weight++;
		return;
	}
}
void Treap_Delete(node*& root,int v){
	if(root==NULL) return;
	if(root->val!=v){
		if(v<root->val) Treap_Delete(root->l,v);
		else Treap_Delete(root->r,v);
		Update_Size(root);
		return;
	}
//	printf("root=%x\troot->weight=%d\n",root,root->weight);
	if(root->weight>1){
		root->weight--;
		root->size--;
		return;
	}
	node* tmp=root;
	if(root->l==NULL&&root->r==NULL){
		root=NULL;
		return;
	}
	if(root->l==NULL&&root->r!=NULL){
		root=tmp->r;
		return;
	}
	if(root->l!=NULL&&root->r==NULL){
		root=tmp->l;
		return;
	}
	if(root->l!=NULL&&root->r!=NULL){
		if(root->l->fix<root->r->fix){
			Right_Rotate(root);
			Treap_Delete(root->r,v);
		}else{
			Left_Rotate(root);
			Treap_Delete(root->l,v);
		}
		Update_Size(root);
		return;
	}
}
int prev_tmp,next_tmp;
int Find_Prev(node* root,int v){
	if(v<=root->val){
		if(root->l!=NULL) return Find_Prev(root->l,v);
	}else{
		prev_tmp=root->val;
		if(root->r!=NULL) Find_Prev(root->r,v);
		return prev_tmp;
	}
}
int Find_Next(node* root,int v){
	if(v>=root->val){
		if(root->r!=NULL) return Find_Next(root->r,v);
	}else{
		next_tmp=root->val;
		if(root->l!=NULL) Find_Next(root->l,v);
		return next_tmp;
	}
}
int Get_The_Kth_Node(node* root,int k){
//	printf("root=%x\n",root);
	int tmp=root->l==NULL?0:root->l->size;
	if(k<=tmp) return (root->l==NULL?1:Get_The_Kth_Node(root->l,k));
	else if(k<=tmp+root->weight) return root->val;
	else return (root->r==NULL?1:Get_The_Kth_Node(root->r,k-(tmp+root->weight)));
	return -1;
}
int Get_Rank(node* root,int v){
//	if(Find_Node(root,v)==NULL) return -1;
	int tmp=root->l==NULL?0:root->l->size;
	if(v==root->val) return tmp+1;
	else if(v<root->val) return (root->l==NULL?1:Get_Rank(root->l,v));
	else return (root->r==NULL?root->size+1:tmp+root->weight+Get_Rank(root->r,v));
}
int n,cmd,t;
node* root;
int main(){
// 	freopen("P3369_in.in","r",stdin);
// 	freopen("P3369_out.out","w",stdout);
	srand(time(0));
	scanf("%d",&n);
	while(n--){
		scanf("%d%d",&cmd,&t);
		if(cmd==1) Treap_Insert(root,t);
		if(cmd==2) Treap_Delete(root,t);
		if(cmd==3) printf("%d\n",Get_Rank(root,t));
		if(cmd==4) printf("%d\n",Get_The_Kth_Node(root,t));
		if(cmd==5) prev_tmp=0,printf("%d\n",Find_Prev(root,t));
		if(cmd==6) next_tmp=0,printf("%d\n",Find_Next(root,t));
	}
}
2024/8/12 16:23
加载中...