萌新求助
查看原帖
萌新求助
503822
Essinsop楼主2021/10/6 07:52

文艺平衡树一开始不插入最大值和最小值的操作是否影响正确性?为什么?

代码:如果不插入2147483647 -2147483647就过不了

#include <bits/stdc++.h>
#define maxn 500005
using namespace std;
int ch[maxn][2], fa[maxn], val[maxn], cnt[maxn], tot, n, sz[maxn], rt, ver[maxn], m;
void maintain(int x) {
	sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];
}
bool get(int x) {
	return x == ch[fa[x]][1];
}
void pushdown(int cur) {
	if(cur && ver[cur]) {
		ver[ch[cur][0]] ^= 1;
		ver[ch[cur][1]] ^= 1;
		swap(ch[cur][0], ch[cur][1]);
		ver[cur] = 0;
	}
}
void rotate(int x) {
	int y = fa[x], z = fa[y], chk = get(x);
	pushdown(x);
	pushdown(y);
	ch[y][chk] = ch[x][chk ^ 1];
	if(ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
	ch[x][chk ^ 1] = y;
	fa[y] = x;
	fa[x] = z;
	if(z) ch[z][y == ch[z][1]] = x;
	maintain(x);
	maintain(y);
}
void splay(int x, int to) {
	for(int f = fa[x];f = fa[x], f != to;rotate(x)) {
		if(fa[f] != to) rotate(get(f) == get(x) ? f : x);
	}
	if(to == 0) rt = x;
}
void ins(int k) {
	if(!rt) {
		val[++tot] = k;
		cnt[tot] = 1;
		rt = tot;
		maintain(tot);
		return;
	}
	int cur = rt, f = 0;
	while(1) {
		if(val[cur] == k) {
			cnt[cur] ++;
			maintain(cur);
			maintain(f);
			splay(cur, 0);
			return;
		}
		f = cur;
		cur = ch[cur][val[cur] < k];
		if(!cur) {
			val[++tot] = k;
			cnt[tot] = 1;
			ch[f][val[f] < k] = tot;
			fa[tot] = f;
			maintain(tot);
			maintain(f);
			splay(tot, 0);
			return;
		}
	}
}
int kth(int k) {
	int cur = rt;
	while(1) {
		pushdown(cur);
		if(ch[cur][0] && sz[ch[cur][0]] >= k) cur = ch[cur][0];
		else {
			k -= (sz[ch[cur][0]] + cnt[cur]);
			if(k <= 0) {
				splay(cur, 0);
				return cur;
			}
			cur = ch[cur][1];
		}
	}
}
void work(int x, int y) {
	int l = kth(x - 1);
	int r = kth(y + 1);
	splay(l, 0);
	splay(r, l);
	int cur = ch[rt][1];
	cur = ch[cur][0];
	ver[cur] ^= 1;
}
void print(int x) {
	pushdown(x);
	if(ch[x][0]) print(ch[x][0]);
	if(val[x] != 2147483647 && val[x] != -2147483647) {
		cout << val[x] << " ";
	}
	if(ch[x][1]) print(ch[x][1]);
}
int main() {
	scanf("%d%d", &n, &m);
	ins(2147483647);
	ins(-2147483647);
	for(int i = 1;i <= n;i++) ins(i);
	while(m --) {
		int l, r;
		scanf("%d%d", &l, &r);
		work(l + 1, r + 1);
	}
	print(rt);
}
2021/10/6 07:52
加载中...