@[LawrenceSivan](/user/375208) 这事 Treap 吗
by Implicit @ 2021-01-24 16:30:14
@[LoveMC](/user/325613) 是的呢
by LawrenceSivan @ 2021-01-24 16:47:27
@[LawrenceSivan](/user/375208) 我和你代码基本相似，也是#12 TLE，请问dalao找到解决方法了吗？
by OvCherryBlossomRain @ 2021-03-15 13:36:20
@[OvCherryBlossomRain](/user/297925)
原因是重载运算符出现了错误
在insert函数中，
```cpp
if(o<o->son[d]){
rotate(o,d^1);
}
```
这个代码片段，这样修改就可以了：
```cpp
if(*o<*o->son[d]){
rotate(o,d^1);
}
```
by LawrenceSivan @ 2021-03-15 15:19:49
@[OvCherryBlossomRain](/user/297925)
已经帮你改好了
修改片段：
由：
```cpp
if(o->son[d]>o) rotate(o,d^1);
```
改成了：
```cpp
if(*o<*o->son[d]) rotate(o,d^1);
```
另一方面，因为您重载的是小于号，所以不要用大于号去比较
by LawrenceSivan @ 2021-03-15 15:24:46
@[OvCherryBlossomRain](/user/297925)
AC代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
struct Node *null;
struct Node{
int size;//size
int rank;
int value;//key
int w;
Node *son[2];
Node(int v){
value = v;
son[0]=son[1]=null;
rank = rand();
size=w=1;
}
bool operator<(const Node& a)const{return rank<a.rank;}
int cmp(int x)const{
if(x==value) return -1;
return x<value?0:1; //0 means left,1 means right
}
void update(){
size = w;
if(son[0]) size +=son[0]->size;
if(son[1]) size +=son[1]->size;
}
};
void rotate(Node* &o,int d){ //d=0,means rotate left,d=1,means rotate right
Node *k = o->son[d^1];
o->son[d^1] = k->son[d];
k->son[d] = o;
o->update();
k->update();
o = k;
}
void insert(Node* &o,int x){ //x insert tree
if(o==null){
o = new Node(x);
}else if(x==o->value){
o->w++;
o->update();
}else{
int d=(x<o->value?0:1);
insert(o->son[d],x);
if(*o<*o->son[d]) rotate(o,d^1);
}
o->update();
}
void remove(Node* &o,int x){//delete x
int d = o->cmp(x);
if(d==-1){
if(o->w>1){
o->w--;
o->update();
return ;
}
Node* u = o;
if(o->son[0]!=null&&o->son[1]!=null){
int d2 = o->son[0]->rank > o->son[1]->rank ? 1:0;
rotate(o,d2);remove(o->son[d2],x);
}else{
if(o->son[0]==null) o = o->son[1];
else o = o->son[0];
delete u;
}
}else{remove(o->son[d],x);}
if(o!=null) o->update();
}
int kth(Node* &o,int k){
if(o==null || k<=0 || k>o->size) return 0;
int d = o->son[0]==null ? 0:o->son[0]->size;
if(k>d && k<=d+o->w){
return o->value;
}else if(k<=d){
return kth(o->son[0],k);
}else{
return kth(o->son[1],k-d-o->w);
}
}
int rank(Node* o,int k,int sum){ //int rank(Node* o,int k,int sum)
if(o==null) return sum+1;
if(k==o->value){
return o->son[0]->size+1+sum;
}else if(k<o->value){
return rank(o->son[0],k,sum);
}else{
return rank(o->son[1],k,sum+o->son[0]->size + o->w);
}
}
int ans;
void pre(Node* o,int k){
if(o==null) return ;
if(k>o->value){
ans = max(ans,o->value);
pre(o->son[1],k);
}else{
pre(o->son[0],k);
}
}
void next(Node* o,int k){
if(o==null) return ;
if(k<o->value){
ans = min(ans,o->value);
next(o->son[0],k);
}else{
next(o->son[1],k);
}
}
int main(){
int q,op,x;
scanf("%d",&q);
null=new Node(0);
null->size=null->w=0;
Node *root=null;
while(q--)
{
scanf("%d%d",&op,&x);
if(op==1) insert(root,x);
else if(op==2) remove(root,x);
else if(op==3) printf("%d\n",rank(root,x,0));
else if(op==4) printf("%d\n",kth(root,x));
else if(op==5) ans=-inf,pre(root,x),printf("%d\n",ans);
else ans=inf,next(root,x),printf("%d\n",ans);
}
return 0;
}
```
by LawrenceSivan @ 2021-03-15 15:25:53
@[LawrenceSivan](/user/375208) 十分感谢，困扰许久，我发现我为了代码格式的好看，我特地将比较换了一下位，原来是重载的问题，太感谢dalao了
by OvCherryBlossomRain @ 2021-03-15 21:22:09