个人感觉是rot挂了?
可能是我经常挂rot, 感觉马蜂挺像, 挂个代码qwq
```
// rotate father first
// double rotate check fa
// ins add fa -> new
// del return null tree
// nxt give p -> p
// kth ls jump continue
#include<bits/stdc++.h>
using namespace std;
const int N = 1000000 + 10;
int tot, root;
struct Splay{
int ch[2], fa, val, cnt, sz;
}t[N];
int ls(int p){return t[p].ch[0];}
int rs(int p){return t[p].ch[1];}
int fa(int p){return t[p].fa;}
void pushup(int p){t[p].sz = t[ls(p)].sz + t[rs(p)].sz + t[p].cnt;}
bool me(int p){return p == rs(fa(p));}
void clear(int p){
t[p].ch[1] = t[p].ch[0] = t[p].sz = t[p].fa = t[p].val = t[p].cnt = 0;
}
void prtree(int p){
if(p == 0) return;
cout << t[p].val << ' ' << t[ls(p)].val << ' ' << t[rs(p)].val << '\n';
prtree(ls(p));
prtree(rs(p));
// cout << '\n';
}
void rotate(int p){
int f = fa(p), ff = fa(fa(p)), b = me(p);
t[f].ch[b] = t[p].ch[!b];
if(t[p].ch[!b]) t[t[p].ch[!b]].fa = f;
t[p].fa = ff;
if(ff) t[ff].ch[me(f)] = p;
t[p].ch[!b] = f;
t[f].fa = p;
pushup(f);
pushup(p);
}
// splay p to root
void splay(int p){
for(int f = fa(p) ; f = fa(p), f ; rotate(p))
if(fa(f)) rotate(me(p) == me(f) ? f : p);
root = p;
}
// ins
void ins(int v){
// prtree(root);
if(!root){
t[++ tot].val = v;
t[tot].cnt = 1;
root = tot;
pushup(tot);
return;
}
int p = root, f = 0;
while(1){
if(t[p].val == v){
t[p].cnt ++;
pushup(p);
pushup(f);
splay(p);
break;
}
f = p;
p = t[p].ch[t[p].val < v];
if(!p){
t[++ tot].val = v;
t[tot].cnt = 1;
t[tot].fa = f;
t[f].ch[t[f].val < v] = tot;
pushup(tot);
pushup(f);
splay(tot);
break;
}
}
}
int rnk(int v){
int p = root, ans = 0;
while(1){
if(v < t[p].val){
p = ls(p);
}
else{
ans += t[ls(p)].sz;
if(t[p].val == v){
splay(p);
return ans + 1;
}
ans += t[p].cnt;
p = rs(p);
}
if(p == 0) return ans + 1;
}
}
int kth(int k){
// prtree(root);
int p = root;
while(1){
if(ls(p) && k <= t[ls(p)].sz){
p = ls(p);
continue;
}
k -= t[ls(p)].sz + t[p].cnt;
if(k <= 0){
splay(p);
return t[p].val;
}
p = rs(p);
}
}
// pre of root
int pre(){
// prtree(root);
int p = ls(root);
if(!p) return 0;
while(rs(p)) p = rs(p);
splay(p);
return p;
}
// nxt of root
int nxt(){
// prtree(root);
int p = rs(root);
if(!p) return 0;
while(ls(p)) p = ls(p);
splay(p);
return p;
}
void del(int k){
// prtree(root);
rnk(k);
if(t[root].cnt > 1){
t[root].cnt --;
pushup(root);
return;
}
if(!ls(root) && !rs(root)){
clear(root);
root = 0;
return;
}
if(!ls(root)){
int p = root;
root = rs(p);
clear(p);
t[root].fa = 0;
return;
}
if(!rs(root)){
int p = root;
root = ls(p);
clear(p);
t[root].fa = 0;
return;
}
int p = root, x = pre();
t[rs(p)].fa = x;
t[x].ch[1] = rs(p);
clear(p);
pushup(p);
}
signed main(){
int n;
cin >> n;
for(int i = 1 ; i <= n ; i ++){
int opt, v;
// cout << '\n';
cin >> opt >> v;
if(opt == 1) ins(v);
if(opt == 2) del(v);
if(opt == 3) cout << rnk(v) << '\n';
if(opt == 4) cout << kth(v) << '\n';
if(opt == 5){ins(v), cout << t[pre()].val << '\n', del(v);}
if(opt == 6){ins(v), cout << t[nxt()].val << '\n', del(v);}
}
}
```
by Pikacu @ 2024-04-02 13:45:26
@[5t0_0r2](/user/999274)
by Pikacu @ 2024-04-02 13:45:50
@[Pikacu](/user/681313) 好像就是交换了一下顺序,改了还是37
by 5t0_0r2 @ 2024-04-02 13:53:22