全是RE
by 大戸アイ @ 2021-04-03 09:45:21
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef class Tree* Miku;
struct Tree
{
int priority,value,leftLeaf;
Miku rightChild,leftChild;
Tree(int value)
{
this->leftChild=this->rightChild=NULL;
this->value=value;
this->priority=rand();
this->leftLeaf=1;
}
~Tree()
{
if(leftChild!=NULL)
delete leftChild;
if(rightChild!=NULL)
delete rightChild;
}
bool operator<(const int x)const{return this->value<x;}
bool operator<=(const int x)const{return this->value<=x;}
bool operator>(const int x)const{return this->value>x;}
bool operator>=(const int x)const{return this->value>=x;}
bool operator==(const int x)const{return this->value==x;}
bool operator<(const Tree x)const{return this->value<x.value;}
};
int n,top;Miku Root=NULL,sets[999];
void leftRotate(Miku &root)
{
Miku tmp=root->rightChild;
root->rightChild=tmp->leftChild;
tmp->leftChild=root;
root=tmp;
root->leftLeaf+=root->leftChild->leftLeaf;
}
void rightRotate(Miku &root)
{
Miku tmp=root->leftChild;
root->leftChild=tmp->rightChild;
tmp->rightChild=root;
root=tmp;
root->rightChild->leftLeaf-=root->leftLeaf;
}
void insert(Miku &now,Miku &x)
{
if(!now)
{
now=x;
return;
}
if(*now<*x)
{
insert(now->rightChild,x);
if(x->priority<now->priority)
leftRotate(now);
}
else
{
insert(now->leftChild,x);
now->leftLeaf++;
if(x->priority<now->priority)
rightRotate(now);
}
}
void del(Miku &now,int x)
{
if(*now<x)
del(now->rightChild,x);
else if(*now>x)
now->leftLeaf--,del(now->leftChild,x);
if(*now==x)
{
Miku *p=&now;
now->leftLeaf--;
while((*p)->leftChild)
{
rightRotate(*p);
p=&((*p)->rightChild);
}
Miku tmp=*p;
*p=(*p)->rightChild;
tmp->leftChild=tmp->rightChild=NULL;
delete tmp;
}
}
int get(Miku now,int x)
{
if(!now)
return 0;
if(*now==x)
return now->leftLeaf;
if(*now<x)
return now->leftLeaf+get(now->rightChild,x);
return get(now->leftChild,x);
}
int search(Miku now,int x)
{
if(now->leftLeaf==x)
return now->value;
if(now->leftLeaf<x)
return search(now->rightChild,x-now->leftLeaf);
return search(now->leftChild,x);
}
int getPrevious(int x)
{
Miku newNode=new Tree(x);
sets[top++]=newNode;
insert(Root,newNode);
int ans = search(Root,get(Root,x)-1);
del(Root,x);
return ans;
}
int getSuccessor(int x)
{
Miku newNode=new Tree(x);
sets[top++]=newNode;
insert(Root,newNode);
int ans = search(Root,get(Root,x)+1);
del(Root,x);
return ans;
}
void operate(int opt)
{
int x;scanf("%d",&x);
if(opt==1)
{
Miku newNode=new Tree(x);
sets[top++]=newNode;
insert(Root,newNode);
}
else if(opt==2) del(Root,x);
else if(opt==3) printf("%d\n", get(Root,x));
else if(opt==4) printf("%d\n", search(Root,x));
else if(opt==5) printf("%d\n", getPrevious(x));
else if(opt==6) printf("%d\n", getSuccessor(x));
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int opt;scanf("%d",&opt);
operate(opt);
}
delete Root;
}
```变成48分了
by 大戸アイ @ 2021-04-03 10:58:15