@[yonghu_3913](/user/820574) `tree[y].l = merge(x,tree[y].l);`
by carrotpp @ 2024-01-07 08:50:30
@[carrotpp](/user/729455) 参数写反了吗?
by yonghu_3913 @ 2024-01-07 09:04:26
[.](https://www.luogu.com.cn/record/142161719)
by yonghu_3913 @ 2024-01-07 09:13:35
@[yonghu_3913](/user/820574)
你原来代码的 merge 和delet 都有写错捏
```
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
struct fhqtreap{
int data;
int pos;
int size;//子树大小
int l,r;
}tree[N];
int tot;
int root = 0;
void pushup(int x){
tree[x].size = tree[tree[x].l].size + tree[tree[x].r].size + 1;
}
int add(int x){
tree[++tot] = {x,rand(),1,0,0};
return tot;
}
void split(int u,int &a,int &b,int val){
if(!u){
a = b = 0;
return;
}
if(tree[u].data <= val){
a = u;
split(tree[a].r,tree[a].r,b,val);
}else{
b = u;
split(tree[b].l,a,tree[b].l,val);
}
pushup(u);
}
void split_siz(int u,int &a,int &b,int siz){
if(!u){
a = b = 0;
return;
}
if(tree[tree[u].l].size + 1 <= siz){
a = u;
split_siz(tree[a].r,tree[a].r,b,siz - 1 - tree[tree[u].l].size);
}else{
b = u;
split_siz(tree[b].l,a,tree[b].l,siz);
}
pushup(u);
}
int merge(int x,int y){
if(!x || !y){
return x + y;
}
if(tree[x].pos < tree[y].pos){
tree[x].r = merge(tree[x].r,y);
pushup(x);
return x;
}else{
tree[y].l = merge(x,tree[y].l);
pushup(y);
return y;
}
}
void insert(int x){
int l,r;
split(root,l,r,x);
root = merge(merge(l,add(x)),r);
}
void delet(int x){
int l,r;
int xa,ya;
split(root,l,r,x);
split_siz(l,xa,ya,tree[l].size - 1);
root = merge(xa,r);
}
int pos(int x){
int l,r;
split(root,l,r,x - 1);
int t = tree[l].size + 1;
root = merge(l,r);
return t;
}
int k(int x,int y){
int p = tree[tree[x].l].size + 1;
if(p == y){
return tree[x].data;
}
if(p < y){
return k(tree[x].r,y - p);
}
return k(tree[x].l,y);
}
int p(int x){
int l,r;
split(root,l,r,x - 1);
int t = k(l,tree[l].size);
root = merge(l,r);
return t;
}
int nxt(int x){
int l,r;
split(root,l,r,x);
int t = k(r,1);
root = merge(l,r);
return t;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int n;
cin >> n;
for(int i = 1;i <= n;i++){
int op;
int x;
cin >> op >> x;
if(op == 1){
insert(x);
}else if(op == 2){
delet(x);
}else if(op == 3){
cout << pos(x) << endl;
}else if(op == 4){
cout <<k(root,x) << endl;
}else if(op == 5){
cout << p(x) << endl;
}else{
cout << nxt(x) << endl;
}
}
}
```
by carrotpp @ 2024-01-07 09:26:27
@[carrotpp](/user/729455) 过了，谢谢
by yonghu_3913 @ 2024-01-07 09:45:25