以下是我的del函数:
void del(int v){
int pre = get_pre(v), suc = get_suc(v);
splay(pre, 0), splay(suc, pre);
int del = ls(suc);
if(ptr[del].cnt > 1) ptr[del].cnt--, ptr[del].siz--, splay(del, 0);
else ls(suc) = 0, splay(suc, 0);
}
在这里面当 if(ptr[del].cnt > 1) 的时候我让 ptr[del].siz--,但是我发现没有这条语句也是对的不知道为什么
以下是我的其他函数:
void pushup(int x){
ptr[x].siz = ptr[ls(x)].siz + ptr[rs(x)].siz + ptr[x].cnt;
}
void rotate(int x){ //旋x,y
int y = ptr[x].p, z = ptr[y].p;
int k = rs(y) == x;
//组x,z
ptr[z].s[rs(z) == y] = x; //swap(x,y)
ptr[x].p = z;
//x.son的调换->y.son
ptr[y].s[k] = ptr[x].s[k^1];
ptr[ptr[x].s[k^1]].p = y;
//组x,y
ptr[x].s[k^1] = y;
ptr[y].p = x;
//先y,后x
pushup(y), pushup(x);
}
void splay(int x, int k){
while(ptr[x].p != k){
int y = ptr[x].p, z = ptr[y].p;
if(z != k) ((ls(z) == y) ^ (ls(y) == x)) ? rotate(x) : rotate(y);
rotate(x);
}
if(k == 0) root = x;
}
void insert(int v){
int x = root, p = 0;
while(x && ptr[x].v != v){
p = x, x = ptr[x].s[v > ptr[x].v];
}
if(x) ptr[x].cnt++;
else{
x = ++idx;
ptr[p].s[v > ptr[p].v] = x;
ptr[x].init(p, v);
}
splay(x, 0);
}
void find(int v){
int x = root;
while(ptr[x].s[v > ptr[x].v] && v != ptr[x].v){
x = ptr[x].s[v > ptr[x].v];
}
splay(x, 0);
}
int get_pre(int v){
find(v);
int x = root;
if(v > ptr[x].v) return x;
x = ls(x);
while(rs(x)) x = rs(x);
splay(x, 0);
return x;
}
int get_suc(int v){
find(v);
int x = root;
if(v < ptr[x].v) return x;
x = rs(x);
while(ls(x)) x = ls(x);
splay(x, 0);
return x;
}