跳跃表，简称跳表。一种链式数据结构，可用于支持平衡树的操作。

【模板】普通平衡树

跳表基于随机化，每个节点以 \(\frac{1}{2}\) 的概率保留一层，\(\frac{1}{4}\) 几率保留两层，依次类推。

期望时间复杂度 \(\mathcal{O}(N\log N)\)​，实际运行不逊于主流平衡树，且具有码量小，便于理解的优点。

如果直接开数组空间复杂度是 \(\mathcal{O}(N\log N)\)​，使用指针或者变长数组 vector 的期望空间复杂度是 \(\sum\limits_{i}2^{-i}N=\mathcal{O}(N)\)。本题前者已经足够。

#define N 100005
#define M 20
struct node{
	int val, nxt[M], sum[M];
}a[N];
#define nt(x, p) a[x].nxt[p]
int idx, u[M];
inline int g(){int s = 0;while(s + 1 < M && (rand() & 4))s ++;return s;}
void ask(int x){
	int p = M - 1, w = 0;
	while(p >= 0){
		while(nt(w, p) && a[nt(w, p)].val < x)w = nt(w, p);
		u[p--] = w;
	}
}
void ins(int x){
	ask(x); int p = 0;
	if(a[nt(u[0], 0)].val == x){
		while(p < M){
			if(a[nt(u[p], p)].val == x)a[nt(u[p], p)].sum[p] ++;
			else a[u[p]].sum[p]++;
			p++;
		}
	}
	else{
		int q = g(), w = nt(u[0], 0);
		a[++idx].sum[0] = 1, a[idx].val = x;
		nt(idx, 0) = w, nt(u[0], 0) = idx;
		rep(i, 1, q){
			a[idx].sum[i] = a[idx].sum[i - 1];
			while(w != nt(u[i], i))a[idx].sum[i] += a[w].sum[i - 1], w = nt(w, i - 1);
			nt(idx, i) = nt(u[i], i), nt(u[i], i) = idx, a[u[i]].sum[i] -= a[idx].sum[i] - 1;
		}
		rep(i, q + 1, M - 1)a[u[i]].sum[i] ++;
	}
}
void del(int x){
	ask(x); int p = 0;
	bool flag = a[nt(u[0], 0)].sum[0] == 1;
	while(p < M){
		if(a[nt(u[p], p)].val == x){
			if(flag) a[u[p]].sum[p] += a[nt(u[p], p)].sum[p] - 1, nt(u[p], p) = a[nt(u[p], p)].nxt[p];
			else a[nt(u[p], p)].sum[p]--;
		}
		else a[u[p]].sum[p]--;
		p++;
	}
}
int Rank(int x){
	int p = M - 1, w = 0, ans = 0;
	while(p >= 0){
		while(nt(w, p) && a[nt(w, p)].val < x)ans += a[w].sum[p], w = nt(w, p);
		p--;
	}
	return ans + a[w].sum[0];
}
int get(int k){
	int p = M - 1, w = 0;
	while(p >= 0){
		while(k >= a[w].sum[p])k -= a[w].sum[p], w = nt(w, p);
		p--;
	}
	return a[w].val;
}
int Nxt(int x){
	ask(x); int p = nt(u[0], 0);
	if(a[p].val == x)return a[nt(p, 0)].val;
	return a[p].val;
}
int Pre(int x){
	ask(x);return a[u[0]].val;
}
int main() {
	srand(time(0));
	int T = read();
	a[0].val = inf_;
	rep(i, 0, M - 1)a[0].sum[i] = 1;
	while(T--){
		int op = read(), x = read();
		if(1 == op)ins(x);
		else if(2 == op)del(x);
		else if(3 == op)printf("%d\n", Rank(x));
		else if(4 == op)printf("%d\n", get(x));
		else if(5 == op)printf("%d\n", Pre(x));
		else printf("%d\n", Nxt(x));
	}
	return 0;
}

【模板】普通平衡树（数据加强版）

同上，实测速度优于主流平衡树，但是第四个点被卡空间。

第四个点全是插入可以特判。

尝试了下 vector 发现空间常数巨大反而是负优化。

指针以后再补

#define N 1000005
#define M 12
struct node{
	int val, nxt[M], sum[M];
}a[N];
#define nt(x, p) a[x].nxt[p]
int idx, u[M];
inline int g(){int s = 0;while(s + 1 < M && (rand() & 3) == 3)s ++;return s;}
void ask(int x){
	int p = M - 1, w = 0;
	while(p >= 0){
		while(nt(w, p) && a[nt(w, p)].val < x)w = nt(w, p);
		u[p--] = w;
	}
}
void ins(int x){
	ask(x); int p = 0;
	if(a[nt(u[0], 0)].val == x){
		while(p < M){
			if(a[nt(u[p], p)].val == x)a[nt(u[p], p)].sum[p] ++;
			else a[u[p]].sum[p]++;
			p++;
		}
	}
	else{
		int q = g(), w = nt(u[0], 0);
		a[++idx].sum[0] = 1, a[idx].val = x;
		nt(idx, 0) = w, nt(u[0], 0) = idx;
		rep(i, 1, q){
			a[idx].sum[i] = a[idx].sum[i - 1];
			while(w != nt(u[i], i))a[idx].sum[i] += a[w].sum[i - 1], w = nt(w, i - 1);
			nt(idx, i) = nt(u[i], i), nt(u[i], i) = idx, a[u[i]].sum[i] -= a[idx].sum[i] - 1;
		}
		rep(i, q + 1, M - 1)a[u[i]].sum[i] ++;
	}
}
void del(int x){
	ask(x); int p = 0;
	bool flag = a[nt(u[0], 0)].sum[0] == 1;
	while(p < M){
		if(a[nt(u[p], p)].val == x){
			if(flag) a[u[p]].sum[p] += a[nt(u[p], p)].sum[p] - 1, nt(u[p], p) = a[nt(u[p], p)].nxt[p];
			else a[nt(u[p], p)].sum[p]--;
		}
		else a[u[p]].sum[p]--;
		p++;
	}
}
int Rank(int x){
	int p = M - 1, w = 0, ans = 0;
	while(p >= 0){
		while(nt(w, p) && a[nt(w, p)].val < x)ans += a[w].sum[p], w = nt(w, p);
		p--;
	}
	return ans + a[w].sum[0];
}
int get(int k){
	int p = M - 1, w = 0;
	while(p >= 0){
		while(k >= a[w].sum[p])k -= a[w].sum[p], w = nt(w, p);
		p--;
	}
	return a[w].val;
}
int Nxt(int x){
	ask(x); int p = nt(u[0], 0);
	if(a[p].val == x)return a[nt(p, 0)].val;
	return a[p].val;
}
int Pre(int x){
	ask(x);return a[u[0]].val;
}
int main() {
	srand(time(0));
	int n = read(), T = read();
	a[0].val = inf_;
	rep(i, 0, M - 1)a[0].sum[i] = 1;
	rp(i, n)ins(read());
	int lastans = 0, xorsum = 0;
	while(T--){
		if(idx >= 900000){puts("0");return 0;}
		int op = read(), x = read() ^ lastans;
		if(1 == op)ins(x);
		else if(2 == op)del(x);
		else {
			if(3 == op)lastans = Rank(x);
			else if(4 == op)lastans = get(x);
			else if(5 == op)lastans = Pre(x);
			else lastans = Nxt(x);
			xorsum ^= lastans;
		}
	}
	cout << xorsum << endl;
	return 0;
}