文艺平衡树

链接

文艺平衡树要求对区间进行修改,这点和线段树很像

我们可以对fhq 平衡树进行小小的变形

题目要求我们对[l,r]进行翻转,我们只需要互换两个节点的编号就行了,由于我们操作的仅仅是1-n的序列,而且编号与值是相对应的,因此我们结构体就不需要开辟出val

而且我们并不知道l对应的具体是什么值,因此split不能按val来裂开,而是根据size裂开

仿照线段树,我们就写一个reverse标记,延迟更新的标记

并用push_down函数更新

还有一个小细节,就是当某个节点发生更改的时候,需要push_down更新

#include<iostream>
#include<random>
using namespace std;
const int MAXN = 1e5 + 5;
struct Node {
	int l, r;
	int size;
	int reverse;
}t[MAXN];
int cnt, root;
int newnode(int val) {
	t[++cnt] = { 0,0,1,0 };
	return cnt;
}
void update(int x) {
	t[x].size = t[t[x].l].size + t[t[x].r].size + 1;
}
void push_down(int now) {
	t[t[now].l].reverse ^= 1;
	t[t[now].r].reverse ^= 1;
    swap(t[now].l, t[now].r);
	t[now].reverse ^= 1;
}
void split(int now, int siz, int& x, int& y) {
	if (!now) x = y = 0;
	else {
		if (t[now].reverse) push_down(now);
		if (t[t[now].l].size < siz) {
			x = now;
			split(t[now].r, siz - 1 - t[t[now].l].size, t[now].r, y);
		}
		else {
			y = now;
			split(t[now].l, siz, x, t[now].l);
		}
		update(now);
	}
}
int merge(int x, int y) {
	if (!x || !y) return x + y;
	if (rand() % (t[x].size + t[y].size) < t[x].size) {
		if (t[x].reverse) push_down(x);
		t[x].r = merge(t[x].r, y);
		update(x);
		return x;
	}
	else {
		if (t[y].reverse) push_down(y);
		t[y].l = merge(x, t[y].l);
		update(y);
		return y;
	}
}
void reverse(int l, int r) {
	int x, y, z;
	split(root, l - 1, x, z);
	split(z, r - l + 1, y, z);
	t[y].reverse ^= 1;
	push_down(y);
	root = merge(merge(x, y), z);
}
void inorder(int now) {
	if (!now) return;
	if (t[now].reverse) push_down(now);
	inorder(t[now].l);
	cout << now << " ";
	inorder(t[now].r);
}
int main() {
	srand(time(nullptr));
	int n, m;
	cin >> n >> m;
	for (int i = 1;i <= n;i++) {
		root = merge(root, newnode(i));
	}
	while (m--) {
		int l, r;
		cin >> l >> r;
		reverse(l, r);
	}
	inorder(root);
}

时间复杂度:O(n log n)

空间复杂度:O(n)