平衡树(Spaly)小结

平衡树是一棵二叉查找树,通过旋转达到左右平衡以保证复杂度。

核心操作:

1,rotate(x),把x提高一位。

2,splay(x, goal),把x旋到指定位置。

(真·小结)

模板-[ZJOI2006]书架

代码
#include <bits/stdc++.h>
#define lc ch[x][0]
#define rc ch[x][1]
using namespace std;
const int MAXN = 100050;
int ch[MAXN][2], fa[MAXN], num[MAXN], pos[MAXN], rt, size[MAXN], cnt, n, m;
int read() {
	char ch; int x = 0, f = 1; while(ch = getchar(), ch < '!' || ch == '-') if(ch == '-') f = -1;
	x = ch - 48; while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48; return x * f;
}
void updpos(int x) {pos[num[x]] = x;}
void pushup(int x) {size[x] = size[rc] + size[lc] + 1; updpos(lc); updpos(rc);}
void rotate(int x) {
	int y = fa[x], z = fa[y], k = (x == ch[y][1]), w = ch[x][k^1];
	fa[w] = y; fa[y] = x; fa[x] = z; ch[x][k^1] = y; ch[y][k] = w; ch[z][(y == ch[z][1])] = x;
	pushup(y); pushup(x);
}
void splay(int x, int goal = 0) {
	for(int y, z; fa[x] != goal; rotate(x))
		if((z = fa[y = fa[x]]) != goal) rotate((y == ch[z][0]) ^ (x == ch[y][0]) ? x : y);
	updpos(x); if(!goal) rt = x;
}
void insert(int key) {
	int x = rt; for(; ch[rt][1]; x = ch[rt][1]);
	fa[++cnt] = x; rc = cnt; num[cnt] = key;
	updpos(cnt); pushup(cnt); splay(cnt);
}
void Top_B(int s, int p) {
	splay(pos[s]); if(!ch[rt][p]) return; 
	if(!ch[rt][p^1]) ch[rt][p^1] = ch[rt][p], ch[rt][p] = 0;
	else {
		int x = ch[rt][p^1]; for(; ch[x][p]; x = ch[x][p]);
		fa[ch[rt][p]] = x; ch[x][p] = ch[rt][p]; ch[rt][p] = 0;
		splay(ch[x][p]);
	}
}
void ask(int s) {splay(pos[s]); printf("%d\n", size[ch[rt][0]]);}
void ist(int t, int s) {
	splay(pos[s]); if(!t) return;
	if(t == 1) {
		int suc = ch[rt][1], ps = pos[s];
		while(ch[suc][0]) suc = ch[suc][0];
		swap(pos[s], pos[num[suc]]);
		swap(num[suc], num[ps]);
	} else {
		int suc = ch[rt][0], ps = pos[s];
		while(ch[suc][1]) suc = ch[suc][1];
		swap(pos[s], pos[num[suc]]);
		swap(num[suc], num[ps]);
	}
}
int qry(int s) {
	int x = rt; 
	while(pos) {
		if(size[lc] +1 == s) return num[x];
		else if(size[lc] >= s) x = lc;
		else s -= size[lc]+1, x = rc;
	}
}
int main() {
	n = read(); m = read();
	for(int i = 1; i <= n; ++i) insert(read());
	while(m--) {
		char opt[10]; scanf("%s", opt);
		if(opt[0] == 'T') Top_B(read(), 0);
		if(opt[0] == 'B') Top_B(read(), 1);
		if(opt[0] == 'I') ist(read(), read());
		if(opt[0] == 'A') ask(read());
		if(opt[0] == 'Q') printf("%d\n", qry(read()));
	}
}

 

 

点赞
  1. Tenalp6174说道:

    你是故意把 Splay 打成 Spaly 吗

发表评论

电子邮件地址不会被公开。 必填项已用*标注

正在获取,请稍候...
00:00/00:00