struct node {
int ch[2],val,id,cnt,siz;
}TR[N];
void up(int cur) {
TR[cur].siz = TR[ls].siz + TR[rs].siz + TR[cur].cnt;
}
void rotate(int &cur,int f) {
int son = TR[cur].ch[f];
TR[cur].ch[f] = TR[son].ch[f ^ 1];
TR[son].ch[f ^ 1] = cur;
up(cur);
cur = son;
up(cur);
}
void insert(int &cur,int val) {
if(!cur) {
cur = ++tot;
TR[cur].val = val;
TR[cur].id = rand();
TR[cur].cnt = TR[cur].siz = 1;
return;
}
TR[cur].siz++;//!!
if(TR[cur].val == val) { TR[cur].cnt++;return;}
int d = val > TR[cur].val;
insert(TR[cur].ch[d],val);
if(TR[TR[cur].ch[d]].id < TR[cur].id) rotate(cur,d);
}
void del(int &cur,int val) {
if(!cur) return;
if(val == TR[cur].val) {
if(TR[cur].cnt > 1) {TR[cur].cnt--;TR[cur].siz--; return;}
if(!ls || !rs) {cur = ls + rs;return;}
int d = TR[rs].id < TR[ls].id;
rotate(cur,d);
del(cur,val);
}
else TR[cur].siz--,del(TR[cur].ch[val > TR[cur].val],val);
}
int Rank(int cur,int val) {
if(!cur) return 0;
if(val == TR[cur].val) return TR[ls].siz + 1;
if(val < TR[cur].val) return Rank(ls,val);
return Rank(rs,val) + TR[ls].siz + TR[cur].cnt;
}
int kth(int cur,int now) {
while(1) {
if(TR[ls].siz >= now) cur = ls;
else if(TR[ls].siz + TR[cur].cnt < now) now -=TR[ls].siz + TR[cur].cnt,cur = rs;
else return TR[cur].val;
}
}
int pred(int cur,int val) {
if(!cur) return -INF;
if(val <= TR[cur].val) return pred(ls,val);//!!!
return max(pred(rs,val),TR[cur].val);
}
int nex(int cur,int val) {
if(!cur) return INF;
if(val >= TR[cur].val) return nex(rs,val);//!!!
return min(nex(ls,val),TR[cur].val);
}
原文:https://www.cnblogs.com/wxyww/p/10041118.html