跳表
人称小平衡树
我们先把跳表入个门。
我们发现很多时候我们能不写平衡树就不写，像有的巨神喜欢用线段树一样（但是线段树的常数我们就不多说了），那我们就也整一点比较怪的东西。我们考虑用链表维护一些平衡树的信息。
最近学了链表之后发现这个东西就是个神，支持很多常数小的操作甚至直接配合其他算法整出各种优越于其他做法的复杂度。所以不例外的，我们用链表维护的速度比大多数平衡树都快。
废话就不多说了，进入正题。
首先介绍一下跳表的核心思想，其实就是通过跳过不必要的细节来达到目标，其思想类似倍增和二进制分组。但是这两个算法都是对于一个数来说的，现在我们是一个数据结构，扩展到了节点与节点之间的连接，我们如何维护？
所以发明跳表的人很明智的想到了通过对链表分层来实现这种跳跃。
具体来说是怎么分层呢？每次我们将一个元素插入，应当在链表中找到恰当的位置，使得链表非严格单调递增。那么为了跳过多余的位置，尽可能多地朝着这个恰当的位置靠拢，我们考虑分层解决。我们如果随机将链表中的一些点拉高，扩展出新的一层，虽然最低的这一层仍然是 $n$ 个元素，但是如果我们先从高层（新的层）进入，然后先在高层找到合适的位置，再从这个位置向下回到底层，再找到这一层中合适的位置。这样我们就达到了目标。
所以说，当我们插入元素的时候，我们以 $p=\frac{1}{2}$ 每层的概率向上扩展，得到一个层数，我们从这个层数开始插入，每层找到合适的位置后向下，更新前后以及向下的链表关系。
code
inline int lever(){
int lv=1;
while((rd()&1) and lv!=32)
++lv;
return lv;
}
inline void ins(int k){
int lv=lever();
if(lv>maxl){
for(int i=maxl+1;i<=lv;++i){
head[i]=newnode();
if(i!=1) p[head[i] ].d=head[i-1];
p[head[i] ].val=-inf;
p[head[i] ].r=newnode();
p[idx].val=inf;
}
maxl=lv;
}
int x=head[lv],id=newnode();
while(lv!=0){
for(;k>=p[p[x].r].val;x=p[x].r);
p[id].val=k;++sz[lv];
p[id].r=p[x].r;p[id].l=x;
p[p[x].r].l=id;p[x].r=id;
if(lv!=1) p[id].d=newnode();
--lv;id=idx;x=p[x].d;
}
}
其实我的写法和网上大多数的都不同，不过可以达到同样的效果（最主要的是网上全是面向工程代码的指针版）
然后删除是类似的，我们从最高层开始向下走，如果这个点权值是我们要删除的，就删，否则就不管它，向下走。
code
inline void del(int k){
int x=head[maxl],lv=maxl;
while(lv!=0){
for(;k>=p[p[x].r].val;x=p[x].r);
int tx=p[x].d;
if(p[x].val==k){
bin[++top]=x;
p[p[x].l].r=p[x].r;
p[p[x].r].l=p[x].l;
--sz[lv];
}
--lv;x=tx;
}
while(!sz[maxl] and maxl>1) --maxl;
}
理解了这些思想，接下来的前驱后继也不难得到
inline int pre(int k){
int x=head[maxl],lv=maxl;
while(lv!=0){
for(;k>p[p[x].r].val;x=p[x].r);
if(lv==1){
return p[x].val;
}
x=p[x].d;--lv;
}
return -inf;
}
inline int nxt(int k){
int x=head[maxl],lv=maxl;
while(lv!=0){
for(;k>=p[p[x].r].val;x=p[x].r);
if(lv==1){
return p[p[x].r].val;
}
x=p[x].d;--lv;
}
return inf;
}
这几个操作全都是 $O(logn)$ 的，而且比平衡树常数小。
其空间复杂度为 $O(n)$。
复杂度证明：
我们发现总共 $n$ 个元素，第 $k$ 层期望有 $\frac{n}{2^{k-1} }$ 个元素。那么空间消耗就是 $n+n/2+n/3+…+n/k=\sum_{i=1}^{k}n/i$
于是有 $\lim_{k\rightarrow+\infty}\sum_{i=1}^{k}n/i=2n$
所以空间复杂度期望是 $O(n)$ 的。可以适当开大一点点，大概开个三倍的样子。
然后基础的跳表就结束了。发现暂时还完全不能代替平衡树。这个我们留到扩展部分解决。
扩展跳表
在此我们就不讲多了，我们仅实现查排名和第k大。如果想了解更多可以看下面的第2篇文章。
其实我们只需要对于一条后继指针维护其跨越的点的数量即可。之后的做法就是经典方法了。现在压力来到维护点数这边。
我们发现只有在插入和删除后会对指针长度造成影响。所以我们考虑在插入和删除的时候维护即可。我们将要更改的点（即后继有变化，或者其下层包含后继有变化的点的点）记录下来，然后从底层开始一层一层暴力修改上去，但是由于只要修改其枚举其最近下层的所属区域，这个速度是很快的。
这样就可以过掉普通平衡树。
code
#include<bits/stdc++.h>
#define ll long long
#define db double
#define filein(a) freopen(#a".in","r",stdin)
#define fileot(a) freopen(#a".out","w",stdout)
#define sky fflush(stdout)
template<class T>
inline void read(T &s){
s=0;char ch=getchar();bool f=0;
while(ch<'0'||'9'<ch) {if(ch=='-') f=1;ch=getchar();}
while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=getchar();}
if(ch=='.'){
int p=10;ch=getchar();
while('0'<=ch&&ch<='9') {s=s+(db)(ch^48)/p;p*=10;;ch=getchar();};
}
s=f?-s:s;
}
const int N=1e5+3;
const int logN=20+3;
const int inf=1e9;
std::mt19937 rd(time(0) );
struct SkipList{
int head[32+3],tail[32+3],sz[32+3];
int idx,maxl;
struct node{
int val,sz;
int l,r,d;
}p[N*3];
inline int lever(){
int lv=1;
while((rd()&1) and lv!=32)
++lv;
return lv;
}
int bin[N*3],top;
inline int newnode(){
return top?bin[top--]:++idx;
}
inline void pushup(int x){
int l=p[x].d,r=p[p[x].r].d,res=0;
if(p[x].val==inf) return;
for(;l!=r;res+=p[l].sz,l=p[l].r);
p[x].sz=res;
}
int pur[2][32+3];
inline void ins(int k){
int lv=lever();
if(lv>maxl){
for(int i=maxl+1;i<=lv;++i){
head[i]=newnode();
if(i!=1) p[head[i] ].d=head[i-1];
p[head[i] ].val=-inf;
tail[i]=newnode();
p[head[i] ].r=tail[i];
p[tail[i] ].val=inf;
if(i!=1) p[tail[i] ].d=tail[i-1];
}
maxl=lv;
}
int limlv=lv;
lv=maxl;
int x=head[lv],id=newnode();
memset(pur,0,sizeof(pur) );
while(lv!=0){
for(;k>=p[p[x].r].val;x=p[x].r);
pur[0][lv]=x;
if(lv<=limlv){
pur[1][lv]=id;
p[id].val=k;++sz[lv];
p[id].r=p[x].r;
p[id].l=x;
p[p[x].r].l=id;p[x].r=id;
if(lv!=1) p[id].d=newnode();
if(lv==1) p[x].sz=p[p[x].r].sz=1;
id=p[id].d;
}
--lv;x=p[x].d;
}
lv=maxl;x=head[maxl];
while(lv!=limlv){
for(;k>=p[p[x].r].val;x=p[x].r);
pur[0][lv]=x;
--lv;x=p[x].d;
}
for(int i=2;i<=maxl;++i){
int tmp=p[pur[0][i] ].sz;
if(pur[0][i]) pushup(pur[0][i]);
if(pur[1][i]) pushup(pur[1][i]);
}
}
inline void del(int k){
int x=head[maxl],lv=maxl;
memset(pur,0,sizeof(pur) );
while(lv!=0){
for(;k>=p[p[x].r].val;x=p[x].r);
int tx=p[x].d;
pur[0][lv]=x;
if(p[x].val==k){
pur[0][lv]=p[x].l;
bin[++top]=x;
p[p[x].l].r=p[x].r;
p[p[x].r].l=p[x].l;
--sz[lv];
}
--lv;x=tx;
}
while(!sz[maxl] and maxl>1) --maxl;
for(int i=2;i<=maxl;++i){
if(pur[0][i]) pushup(pur[0][i]);
}
}
inline int pre(int k){
int x=head[maxl],lv=maxl;
while(lv!=0){
for(;k>p[p[x].r].val;x=p[x].r);
if(lv==1){
return p[x].val;
}
x=p[x].d;--lv;
}
return -inf;
}
inline int nxt(int k){
int x=head[maxl],lv=maxl;
while(lv!=0){
for(;k>=p[p[x].r].val;x=p[x].r);
if(lv==1){
return p[p[x].r].val;
}
x=p[x].d;--lv;
}
return inf;
}
inline int at(int k){
int x=head[maxl],lv=maxl;
while(lv!=0){
for(;p[x].sz<=k;k-=p[x].sz,x=p[x].r);
if(lv==1){
return p[x].val;
}
x=p[x].d;--lv;
}
return inf;
}
inline int rk(int k){
int x=head[maxl],lv=maxl,res=0;
while(lv!=0){
for(;k>p[p[x].r].val;res+=p[x].sz,x=p[x].r);
if(lv==1) {
return res+1;
}
x=p[x].d;--lv;
}
return inf;
}
inline void show(){
for(int i=maxl;i>=1;--i){
if(!sz[i]) continue;
printf("[%d]",i);
for(int x=head[i];;x=p[x].r){
if(p[x].val==inf){
printf("inf[%d](%d,%d,%d,%d)\n",p[x].sz,x,p[x].d,p[x].r,p[x].l);
break;
}
else if(p[x].val==-inf) printf("-inf[%d](%d,%d,%d,%d) ",p[x].sz,x,p[x].d,p[x].r,p[x].l);
else printf("%d[%d](%d,%d,%d,%d) ",p[x].val,p[x].sz,x,p[x].d,p[x].r,p[x].l);
}
}
putchar('\n');
}
}s;
int n;
int main(){
filein(a);fileot(a);
read(n);
for(int i=1;i<=n;++i){
int opt,x;
read(opt);read(x);
if(opt==1){
s.ins(x);
}else if(opt==2){
s.del(x);
}else if(opt==3){
printf("%d\n",s.rk(x) );
}else if(opt==4){
printf("%d\n",s.at(x) );
}else if(opt==5){
printf("%d\n",s.pre(x) );
}else if(opt==6){
printf("%d\n",s.nxt(x) );
}
}
return 0;
}
但是常数还是不如替罪羊。小数据下跑得比较快，数据太大就慢起来了。
然后我们发现一层以上的点是拥有统治区间的，其长度为我们之前维护的前向指针的长度（自身到下一个节点之前）。所以跳表也是支持区间操作的。默认是支持单点修区间查。但是也可以通过一些美妙的操作来使其支持区间修单点查,甚至区间修区间查。显然 $tag$ 什么也是可以打的，区间翻转什么的说不定也是可以的。这些扩展我们暂且不讨论，有兴趣可以研究一下。