传送门：洛谷 - P3369
题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
- 插入$x$
- 删除$x$,如果有多个数，删除一个
- 查询$x$的排名
- 查询排名为$x$的数
- 查询$x$的前驱
- 查询$x$的后继
输入描述
第一行为 $n$，表示操作的个数,下面 $n$ 行每行有两个数 $opt$ 和 $x$，$opt$ 表示操作的序号$( 1≤opt≤6 )$
输出描述
输出对应的答案
思路分析
按权值分裂
样例输入
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
样例输出
106465
84185
492737
Splay代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
bool IOerror=0;
inline char nc() {
static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
if(p1==pend) {
p1=buf;
pend=buf+fread(buf,1,BUF_SIZE,stdin);
if(pend==p1) {
IOerror=1;
return -1;
}
}
return *p1++;
}
inline bool blank(char ch) {
return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
}
template<class T> inline bool read(T &x) {
bool sign=0;
char ch=nc();
x=0;
for(; blank(ch); ch=nc());
if(IOerror)return false;
if(ch=='-')sign=1,ch=nc();
for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
if(sign)x=-x;
return true;
}
template<class T,class... U>bool read(T& h,U&... t) {
return read(h)&&read(t...);
}
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 0x3f3f3f3f;
const int N = 1e6+10;
struct node {
int siz,fa,sum,val,ch[2];
void clear() {
siz=fa=sum=val=ch[0]=ch[1]=0;
}
} tree[N];
int root,cnt;
#define ls tree[x].ch[0]
#define rs tree[x].ch[1]
#define ident(x,f) tree[f].ch[1]==x
void pp(int x) {
tree[x].siz=tree[ls].siz+tree[rs].siz+tree[x].sum;
}
void connect(int x,int f,int s) {
tree[f].ch[s]=x;
tree[x].fa=f;
}
void rotate(int x) {
int f=tree[x].fa;
int ff=tree[f].fa;
int fs=ident(x,f);
int ffs=ident(f,ff);
connect(tree[x].ch[fs^1],f,fs);
connect(x,ff,ffs);
connect(f,x,fs^1);
pp(f);
pp(x);
}
void splay(int x,int top) {
if(!top) root=x;
while(tree[x].fa!=top) {
int f=tree[x].fa;
int ff=tree[f].fa;
if(ff!=top) ident(x,f)^ident(f,ff) ? rotate(x):rotate(f);
rotate(x);
}
}
void newnode(int &x,int fa,int val) {
x = ++cnt;
tree[x].clear();
tree[x].fa=fa;
tree[x].val=val;
tree[x].siz=tree[x].sum=1;
}
void delnode(int x) {
splay(x,0);
if(tree[x].sum>1) {
tree[x].sum--;
return ;
}
if(tree[x].ch[1]) {
int p = tree[x].ch[1];
while(tree[p].ch[0]) p=tree[p].ch[0];
splay(p,x);
connect(tree[x].ch[0],p,0);
root=p;
tree[root].fa=0;
pp(root);
} else {
root=tree[x].ch[0];
tree[root].fa=0;
}
}
void ins(int &x,int fa,int val) {
if(!x) {
newnode(x,fa,val);
splay(x,0);
} else if(val<tree[x].val) {
ins(ls,x,val);
} else if(val>tree[x].val) {
ins(rs,x,val);
} else {
tree[x].sum++;
splay(x,0);
}
}
void del(int x,int val) {
if(val>tree[x].val) del(rs,val);
else if(val<tree[x].val) del(ls,val);
else delnode(x);
}
int getrank(int val) {
int x = root;
int rank = 1;
while(x) {
if(tree[x].val == val) {
rank+=tree[ls].siz;
splay(x,0);
break;
}
if(val > tree[x].val) {
rank+=tree[ls].siz+tree[x].sum;
x=tree[x].ch[1];
} else {
x=tree[x].ch[0];
}
}
return rank;
}
int getnum(int rank) {
int x=root;
while(x) {
int lsiz = tree[ls].siz;
if(lsiz+1 <=rank && rank<=lsiz+tree[x].sum) {
splay(x,0);
break;
}
if(lsiz<rank) {
rank -=lsiz+tree[x].sum;
x=tree[x].ch[1];
} else {
x=tree[x].ch[0];
}
}
return tree[x].val;
}
void print(int x) {
printf("%d\n",x);
}
int main() {
#ifdef xiaofan
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int T;
read(T);
while(T--) {
int op,x;
read(op,x);
switch(op) {
case 1:
ins(root,0,x);
break;
case 2:
del(root,x);
break;
case 3:
print(getrank(x));
break;
case 4:
print(getnum(x));
break;
case 5:
print(getnum(getrank(x)-1));
break;
case 6:
print(getnum(getrank(x+1)));
break;
}
}
return 0;
}
fhq treap代码
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
using namespace std;
const int INF = 0x3f3f3f3f;
const int N= 1e5+10;
struct ndoe {
int l,r;
int key,val;
int size;
} tree[N];
int cnt,root;
int newnode(int val) {
tree[++cnt].val=val;
tree[cnt].key=rand();
tree[cnt].size=1;
return cnt;
}
void update(int now) {
tree[now].size=tree[tree[now].l].size+tree[tree[now].r].size+1;
}
void split(int now,int val,int &x,int &y) {
if(!now) x=y=0;
else {
if(tree[now].val<=val) {
x=now;
split(tree[now].r,val,tree[x].r,y);
} else {
y=now;
split(tree[now].l,val,x,tree[y].l);
}
update(now);
}
}
int merge(int x,int y) {
if(!x||!y)
return x+y;
if(tree[x].key>tree[y].key) {
tree[x].r=merge(tree[x].r,y);
update(x);
return x;
} else {
tree[y].l=merge(x,tree[y].l);
update(y);
return y;
}
}
int x,y,z;
void ins(int val) {
split(root,val,x,y);
root=merge(merge(x,newnode(val)),y);
}
void del(int val) {
split(root,val,x,z);
split(x,val-1,x,y);
y=merge(tree[y].l,tree[y].r);
root=merge(merge(x,y),z);
}
void getrank(int val) {
split(root,val-1,x,y);
cout<<tree[x].size+1<<endl;
root=merge(x,y);
}
void getnum(int rank) {
int now=root;
while(now) {
if(tree[tree[now].l].size+1==rank)
break;
else if(tree[tree[now].l].size>=rank)
now=tree[now].l;
else {
rank-=tree[tree[now].l].size+1;
now=tree[now].r;
}
}
cout<<tree[now].val<<endl;
}
void pre(int val) {
split(root,val-1,x,y);
int now=x;
while(tree[now].r)
now=tree[now].r;
cout<<tree[now].val<<endl;
root=merge(x,y);
}
void nxt(int val) {
split(root,val,x,y);
int now=y;
while(tree[now].l)
now=tree[now].l;
cout<<tree[now].val<<endl;
root=merge(x,y);
}
int main() {
IOS;
#ifdef xiaofan
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
cin>>t;
while(t--) {
int opt,x;
cin>>opt>>x;
switch(opt) {
case 1:
ins(x);
break;
case 2:
del(x);
break;
case 3:
getrank(x);
break;
case 4:
getnum(x);
break;
case 5:
pre(x);
break;
case 6:
nxt(x);
break;
}
}
return 0;
}
