【ybt金牌導航4-5-1】【luogu P3369】普通平衡樹（替罪羊樹做法）

普通平衡樹

題目連結：ybt金牌導航4-5-1 / luogu P3369

題目大意

平衡樹模闆題，要求維護一些操作。

插入一個數，删除一個數，查詢一個數的排名，查詢排名一直的數，找前驅後繼。

思路

這個其實是模闆題，可以有各種解法。

現在在學替罪羊樹，就用替罪羊樹來做了。

後面有空的話應該會弄一個平衡樹合集。

替罪羊其實就是弄一個限度，如果對于一個點，它的某個子樹的點的個數占了這個點對應子樹點個數的一定量的時候，就需要暴力重構它對應的樹，把它的深度弄小。

弄成什麼最小呢？沒錯，就是盡可能弄成每個點兩個子樹的個數相同的情況。

對于看是否要重構的那個量，我們一般會設 0.6 ∼ 0.7 0.6\sim0.7 0.6∼0.7。

然後就來看看如何暴力重構。

首先，它就要兩個子樹大小相同，那假設你還原出來數組，那就是每次折半，前面的給左子樹，後面的給右子樹。

那怎麼找到子樹呢？我們可以用中序周遊，因為平衡樹有二叉搜尋樹的性質。

然後你再按先序周遊把重構的樹裡面的點都找出來，然後你每次折半找子樹的時候，就拿出一個來作為這個子樹的根。

然後其他操作就很暴力，就不多說了，看代碼吧。

代碼

//替罪羊

#include<cstdio>
#define alpha 0.7

using namespace std;

struct Tree {
	int l, r, val, fa, num, sum;
}tree[1000001];
struct reTree {
	int val, num;
}retree[100001];
int n, op, x, root, sta[100001];
int maxn, tot, tott;

bool check(int x) {//判斷是否失衡
	if (!tree[x].num) return 0;
	if (tree[tree[x].l].sum >= (double)(alpha * tree[x].sum)) return 1;
	if (tree[tree[x].r].sum >= (double)(alpha * tree[x].sum)) return 1;
	return 0;
}

void up(int now) {//向上傳遞值
	tree[now].sum = tree[now].num;
	if (tree[now].l) tree[now].sum += tree[tree[now].l].sum;
	if (tree[now].r) tree[now].sum += tree[tree[now].r].sum;
}

void dfs(int x) {//dfs把樹拍扁，好重構
	sta[++sta[0]] = x;//記錄點的編号
	if (tree[x].l) dfs(tree[x].l);
	if (tree[x].num) {//按中序周遊記錄值
		retree[++tott].val = tree[x].val;
		retree[tott].num = tree[x].num;
	}
	tree[x].sum = 0;
	if (tree[x].r) dfs(tree[x].r);
}

int get_new() {//把你拍扁的點取出來
	if (sta[0]) {
		sta[0]--;
		return sta[sta[0] + 1];
	}
	else return ++tot;
}

void make_new(int l, int r, int now, int father) {//重構一個最平衡的樹
	int mid = (l + r) >> 1;
	tree[now].fa = father;
	tree[now].num = retree[mid].num;
	tree[now].val = retree[mid].val;
	tree[now].sum = 1;
	if (l <= mid - 1) {
		tree[now].l = get_new();
		make_new(l, mid - 1, tree[now].l, now);
	}
	else tree[now].l = 0;
	if (r >= mid + 1) {
		tree[now].r = get_new();
		make_new(mid + 1, r, tree[now].r, now);
	}
	else tree[now].r = 0;
	up(now);
}

void rebuild(int x) {//暴力重構樹
	if (!x) return ;
	tott = 0;
	dfs(x);//拍扁，搞粗中序周遊
	int now = get_new();
	if (x == root) root = now;
	tree[now].fa = tree[x].fa;
	int mid = (1 + tott) >> 1;//先把要重構的樹的根弄了
	if (retree[mid].val < tree[tree[now].fa].val) tree[tree[now].fa].l = now;
		else tree[tree[now].fa].r = now;
	make_new(1, tott, now, tree[now].fa);
}

void insert(int x, bool need_build) {//插入點
	if (root == 0) {
		root = 1;
		tot = 1;
		tree[1] = (Tree){0, 0, x, 0, tree[1].num + 1, tree[1].sum + 1};
		return ;
	}
	
	int now = root;
	while (tree[now].sum) {//一直跑跑到插入的位置
		if (x == tree[now].val) {//之前出現過，直接加個數
			tree[now].num++;
			tree[now].sum++;
			return ;
		}
		if (!tree[now].l && x < tree[now].val) break;//新的邊，要重建立
		if (!tree[now].r && x > tree[now].val) break;
		tree[now].sum++;
		if (x < tree[now].val) now = tree[now].l;
			else if (x > tree[now].val) now = tree[now].r;
	}
	if (x == tree[now].val) {//之前出現過，直接加個數
		tree[now].num++;
		tree[now].sum++;
		return ;
	}
	
	tree[now].sum++;
	
	int tmp = now;//建立新的點，并且完善值和它父親的兒子的值
	if (x < tree[now].val) now = tree[now].l = ++tot;
		else if (x > tree[now].val) now = tree[now].r = ++tot;
	tree[now].num++;
	tree[now].sum++;
	tree[now].val = x;
	if (tmp != now) tree[now].fa = tmp;
	
	int first_fix = 0;//判斷樹是否需要重構
	while (now != root) {
		now = tree[now].fa;
		if (check(now)) first_fix = now;
	}
	if (need_build && first_fix) rebuild(first_fix);
}

int tree_place(int x) {//查找一個值在樹上的位置
	int now = root;
	while (tree[now].val != x && tree[now].sum != 0) {
		if (x <= tree[now].val) now = tree[now].l;
			else now = tree[now].r;
	}
	return now;
}

void delete_(int x, int need_build) {//删去一個點
	tree[x].num--;
	tree[x].sum--;
	int first_fix = 0;//判斷是否需要重構
	while (x != root) {
		x = tree[x].fa;
		tree[x].sum--;
		if (check(x)) first_fix = x;
	}
	
	if (need_build && first_fix) rebuild(first_fix);
}

int get_rank(int x) {//得到排名
    insert(x, 0);//因為待會會删掉，是以不用重構
	int now = tree_place(x);
	int re = tree[tree[now].l].sum + 1;
	while (now != root) {
		if (tree[tree[now].fa].r == now)
			re += tree[tree[tree[now].fa].l].sum + tree[tree[now].fa].num;
		now = tree[now].fa;
	}
	delete_(tree_place(x), 0);
	return re;
}

int get_num(int x) {//得到排名對于的值
	int now = root;
	while (x) {
		if (x <= tree[tree[now].l].sum) now = tree[now].l;
			else if (x <= tree[tree[now].l].sum + tree[now].num) return tree[now].val;
				else {
					x -= tree[tree[now].l].sum + tree[now].num;
					now = tree[now].r;
				}
	}
	return tree[now].fa;
}

int pre(int x) {//前驅
	insert(x, 0);
	int need_rank = get_rank(x) - 1;
	delete_(tree_place(x), 0);
	return get_num(need_rank);
}

int suc(int x) {//後繼
	insert(x + 1, 0);
	int need_rank = get_rank(x + 1);
	delete_(tree_place(x + 1), 0);
	return get_num(need_rank);
}

int main() {
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &op, &x);
		

		if (op == 1) {
			insert(x, 1);
			continue;
		}
		if (op == 2) {
			delete_(tree_place(x), 1);
			continue;
		}
		if (op == 3) {
			printf("%d\n", get_rank(x));
			continue;
		}
		if (op == 4) {
			printf("%d\n", get_num(x));
			continue;
		}
		if (op == 5) {
			printf("%d\n", pre(x));
			continue;
		}
		if (op == 6) {
			printf("%d\n", suc(x));
			continue;
		}
	}
	
	return 0;
}