【ybt金牌導航4-7-5】【luogu P3380】【模闆】二逼平衡樹（樹套樹）

【模闆】二逼平衡樹（樹套樹）

題目連結：ybt金牌導航4-7-5 / luogu P3380

題目大意

要你支援一些操作。

求一個數的區間排名，一個區間的排名第 k，修改數組的一個數，求一個區間中一個數的前驅後繼。

思路

考慮到它有了一個區間，我們不能直接用平衡樹來搞。

那我們就有一個想法，用一個方法表示出所有區間，都建一個平衡樹。

當然會鍋。

那我們想一下，你其實可以把它分成幾個區間——線段樹。

然後就想到了線段樹套平衡樹的做法。

線段樹記錄位置，然後每個節點都是一個平衡樹。

一開始建就直接枚舉它覆寫的範圍，直接一個一個數插入。

（我們這裡用的是 fhq Treap）

然後你區間排名就是把那些關聯的平衡樹都找出來，看裡面總共有多少個數小于這個數。然後這個個數加一就是排名。

（我這裡用的是小于等于，是以要看有多少個小于等于 x − 1 x-1 x−1 的再加一）

接着是求排名第 k，我們并沒有什麼優秀的方法，是以我們二分這個數，然後看排名是否小于等于 k。

（這個地方就是 n l o g 3 n nlog^3n nlog3n，比較不優，聽說可以權值線段樹套平衡樹，線段樹記錄數值，平衡樹記錄範圍，但我不會搞）

然後修改，那我們就把包含它的區間（線段樹上到這個點的鍊）都找出來處理，先把之前的數删掉，然後再插入。

删掉的話我們隻删一個，是以我們把這個大小的數字（們）組成的平衡樹割出來，然後隻用删一個，就把根節點删掉（把左右兒子合并）就好了。

然後就是前驅後繼，那也是同樣的方法，在每個分割出的區間都求一次，然後取最大 / 最小值就可以。

記得處理沒有前驅沒有後繼的情況。

代碼

#include<queue>
#include<cstdio>
#include<cstdlib>
#include<iostream>

using namespace std;

int n, m, a[50001], root, tot;
int op, x, y, z;
struct Tree_in {
	int ls, rs, sz, yj, val;
}tree[4000001];
struct Tree_out {
	int rt;
}t[200001];

int newpoint(int num) {
	int re = ++tot;
	tree[re] = (Tree_in){0, 0, 1, rand(), num};
	return re;
}

void up(int now) {
	tree[now].sz = tree[tree[now].ls].sz + tree[tree[now].rs].sz + 1;
}

pair <int, int> split_val(int now, int val) {
	if (!now) return make_pair(0, 0);
	
	pair <int, int> re;
	if (val < tree[now].val) {
		re = split_val(tree[now].ls, val);
		tree[now].ls = re.second;
		up(now);
		re.second = now;
	}
	else {
		re = split_val(tree[now].rs, val);
		tree[now].rs = re.first;
		up(now);
		re.first = now;
	}
	
	return re;
}

int merge(int x, int y) {
	if (!x) return y;
	if (!y) return x;
	
	if (tree[x].yj < tree[y].yj) {
		tree[x].rs = merge(tree[x].rs, y);
		up(x);
		return x;
	}
	else {
		tree[y].ls = merge(x, tree[y].ls);
		up(y);
		return y;
	}
}

void insert_(int &now, int num) {
	pair <int, int> x = split_val(now, num);
	now = merge(merge(x.first, newpoint(num)), x.second);
}

int ask_bigger_(int &now, int num) {
	pair <int, int> x = split_val(now, num); 
	int re = tree[x.first].sz;
	now = merge(x.first, x.second);
	return re;
}

void delete_(int &now, int num) {
	pair <int, int> x = split_val(now, num);
	pair <int, int> y = split_val(x.first, num - 1);
	y.second = merge(tree[y.second].ls, tree[y.second].rs);
	//删掉的話這裡是隻删一個，對了防止多個相同的都被删，我們把這些數組成的平衡樹割出來，然後把它的根節點丢掉（即把左右兒子合并，就可以隻删一個）
	now = merge(merge(y.first, y.second), x.second); 
}

int ask_pre_(int &now, int num) {
	pair <int, int> x = split_val(now, num - 1);
	int X = x.first, lst = -2147483647;
	while (X) {
		lst = X;
		X = tree[X].rs;
	}
	now = merge(x.first, x.second);
	if (lst == -2147483647) return lst; 
	return tree[lst].val;
}

int ask_nxt_(int &now, int num) {
	pair <int, int> x = split_val(now, num);
	int X = x.second, lst = 2147483647;
	while (X) {
		lst = X;
		X = tree[X].ls;
	}
	now = merge(x.first, x.second);
	if (lst == 2147483647) return lst;
	return tree[lst].val;
}

void build(int now, int l, int r) {
	if (l == r) {
		t[now].rt = newpoint(a[l]);
		return ;
	}
	else {
		for (int i = l; i <= r; i++)//每個點枚舉它覆寫的範圍，一個一個加
			insert_(t[now].rt, a[i]);
	}
	
	int mid = (l + r) >> 1;
	build(now << 1, l, mid);
	build(now << 1 | 1, mid + 1, r);
}

int ask_bigger(int now, int l, int r, int L, int R, int num) {//記得排名要加一個，而且這裡是大于等于 num 的個數
	if (L <= l && r <= R) {
		return ask_bigger_(t[now].rt, num);
	}
	
	int re = 0, mid = (l + r) >> 1;
	if (L <= mid) re += ask_bigger(now << 1, l, mid, L, R, num);
	if (mid < R) re += ask_bigger(now << 1 | 1, mid + 1, r, L, R, num);
	
	return re;
}

int ask_kth(int l, int r, int rnk) {
	int L = 0, R = 1e8, ans = 0;
	while (L <= R) {
		int mid = (L + R) >> 1;
		if (ask_bigger(1, 1, n, l, r, mid - 1) + 1 <= rnk) {
			ans = mid;
			L = mid + 1;
		}
		else R = mid - 1;
	}
	return ans;
}

void change(int now, int l, int r, int pl, int num) {
	delete_(t[now].rt, a[pl]);//交換的就跑出有影響的所有區間（線段樹上到它的鍊）
	insert_(t[now].rt, num);//然後删掉之前的，放上現在的
	
	if (l == r) return ;
	
	int mid = (l + r) >> 1;
	if (pl <= mid) change(now << 1, l, mid, pl, num);
		else change(now << 1 | 1, mid + 1, r, pl, num);
}

int ask_pre(int now, int l, int r, int L, int R, int num) {
	if (L <= l && r <= R) {
		return ask_pre_(t[now].rt, num);
	}
	
	int mid = (l + r) >> 1, re = -2147483647;
	if (L <= mid) re = max(re, ask_pre(now << 1, l, mid, L, R, num));
	if (mid < R) re = max(re, ask_pre(now << 1 | 1, mid + 1, r, L, R, num));
	
	return re; 
}

int ask_nxt(int now, int l, int r, int L, int R, int num) {
	if (L <= l && r <= R) {
		return ask_nxt_(t[now].rt, num);
	}
	
	int mid = (l + r) >> 1, re = 2147483647;
	if (L <= mid) re = min(re, ask_nxt(now << 1, l, mid, L, R, num));
	if (mid < R) re = min(re, ask_nxt(now << 1 | 1, mid + 1, r, L, R, num));
	
	return re;
}

int main() {
	srand(19491001);
	
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	
	build(1, 1, n);
	
	while (m--) {
		scanf("%d", &op);
		
		if (op == 1) {
			scanf("%d %d %d", &x, &y, &z);
			printf("%d\n", ask_bigger(1, 1, n, x, y, z - 1) + 1);
			continue;
		}
		if (op == 2) {
			scanf("%d %d %d", &x, &y, &z);
			printf("%d\n", ask_kth(x, y, z));
			continue;
		}
		if (op == 3) {
			scanf("%d %d", &x, &y);
			change(1, 1, n, x, y);
			a[x] = y;
			continue;
		}
		if (op == 4) {
			scanf("%d %d %d", &x, &y, &z);
			printf("%d\n", ask_pre(1, 1, n, x, y, z));
			continue;
		}
		if (op == 5) {
			scanf("%d %d %d", &x, &y, &z);
			printf("%d\n", ask_nxt(1, 1, n, x, y, z));
			continue;
		}
	}
	
	return 0;
}