本地运行的时候没有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));
}
}