【ybt金牌導航4-3-2】【luogu P3391】【模闆】文藝平衡樹

【模闆】文藝平衡樹

題目連結：ybt金牌導航4-3-2 / luogu P3391

題目大意

給一個數列，會有一些操作，把裡面的一個區間翻轉。

要你輸出最後數列的樣子。

思路

區間翻轉，自然會想到這個是平衡樹可以實作的操作。

然後怎麼實作呢？其實就是把左邊界的左邊拎到根，右邊界的右邊拎到根的右兒子，然後從根右兒子的左兒子開始遞歸。

（這裡左右邊界的左右邊不是直接讀入的加減，而是求第幾大的位置，因為你平衡樹裡面記的下标是數字，而不是位置）

每到一個點，就把左右兒子交換，然後繼續遞歸兩個兒子。

但是如果你每次都遞歸會逾時，我們考慮用懶标記。

你就直接打标記，然後每次要下放的時候就翻轉左右子樹，然後給左右子樹打标記，再清除自己的标記。

（别的操作不用管，也不要用，都不确定是否正确）

代碼

#include<cstdio>
#include<iostream>

using namespace std;

struct Tree {
	int l, r, fa, val, size;
	bool lazy;
}tree[1000001];
int n, m, a[100003], x, y, root, tot;
int lef_root, rig_root;

bool son__p(int now) {
	return tree[tree[now].fa].l == now;
}

void up(int now) {//更新大小
	tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;
}

void down(int now) {//lazy标記
	if (tree[now].lazy) {
		tree[tree[now].l].lazy ^= 1;
		tree[tree[now].r].lazy ^= 1;
		swap(tree[now].l, tree[now].r);
		tree[now].lazy = 0;
	}
}

void rotate(int now) {//旋轉
	int father = tree[now].fa;
	int grand = tree[father].fa;
	int son = son__p(now) ? tree[now].r : tree[now].l;
	
	down(father);
	down(now);
	
	if (grand) son__p(father) ? tree[grand].l = now : tree[grand].r = now;
	if (son__p(now)) tree[now].r = father, tree[father].l = son;
		else tree[now].l = father, tree[father].r = son;
	tree[now].fa = grand;
	tree[father].fa = now;
	if (son) tree[son].fa = father;
	
	up(father);
	up(now);
}

void splay(int x, int target) {//splay上提操作
	while (tree[x].fa != target) {
		if (tree[tree[x].fa].fa != target) {
			son__p(x) == son__p(tree[x].fa) ? rotate(tree[x].fa) : rotate(x);
		}
		rotate(x);
	}
	
	if (!target) root = x;
}

int find(int x) {
	int now = root;
	while (now) {
		if (x == tree[now].val) break;
		if (x >= tree[now].val) now = tree[now].r;
			else now = tree[now].l;
	}
	if (now != root) splay(now, 0);
	return now;
}

int find_kth(int k) {//查詢第k大的點的編号
	int now = root;
	while (now) {
		down(now);
		if (k <= tree[tree[now].l].size) now = tree[now].l;
			else {
				k -= tree[tree[now].l].size + 1;
				if (!k) return now;
				now = tree[now].r;
			}
	}
}

void insert(int x) {
	int now = root, last = 0;
	while (now) {
		last = now;
		tree[now].size++;
		if (x < tree[now].val) now = tree[now].l;
			else now = tree[now].r;
	}
	
	tot++;
	tree[tot].fa = last;
	tree[tot].val = x;
	tree[tot].size = 1;
	if (x < tree[last].val) tree[last].l = tot;
		else tree[last].r = tot;
	
	splay(tot, 0);
}

void join(int small, int big) {
	tree[small].fa = tree[big].fa = 0;
	int new_root = small;
	while (tree[new_root].r)
		new_root = tree[new_root].r;
	splay(new_root, 0);
	tree[new_root].r = big;
	tree[big].fa = new_root;
}

void delete_(int x) {
	splay(x, 0);
	if (!tree[x].l && tree[x].r) tree[tree[x].r].fa = 0;
		else if (tree[x].l && !tree[x].r) tree[tree[x].l].fa = 0;
			else join(tree[x].l, tree[x].r);
	
	tree[x].l = tree[x].r = 0;
}

int get_rank(int x) {
	int now = find(x);
	return tree[tree[now].l].size + 1;
}

void spilt(int x) {
	int no_root = find(x);
	lef_root = tree[no_root].l;
	rig_root = tree[no_root].r;
	tree[no_root].l = tree[no_root].r = 0;
}

int pre(int x) {
	int now = root;
	now = tree[now].l;
	if (!now) return -1;
	while (tree[now].r) {
		now = tree[now].r;
	}
	return tree[now].val;
}

int nxt(int x) {
	int now = root;
	now = tree[now].r;
	if (!now) return -1;
	while (tree[now].l) {
		now = tree[now].l;
	}
	return tree[now].val;
}

int build(int now, int l, int r) {//建造初始平衡樹（根據原始序列）
	if (l > r) return 0;
	int mid = (l + r) >> 1;
	tree[++tot].fa = now;
	now = tot;
	tree[now].lazy = 0;
	tree[now].val = a[mid];
	tree[now].l = build(now, l, mid - 1);
	tree[now].r = build(now, mid + 1, r);
	up(now);
	return now;
}

void write(int now) {//輸出最後的數組
	down(now);
	
	if (tree[now].l) write(tree[now].l);
	if (tree[now].val != -1e9 && tree[now].val != 1e9)
		printf("%d ", tree[now].val);
	if (tree[now].r) write(tree[now].r);
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) a[i + 1] = i;
	a[1] = -1e9;
	a[n + 2] = 1e9;
	
	root = build(0, 1, n + 2);
	
	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &x, &y);
		
		x = find_kth((x + 1) - 1);
		y = find_kth((y + 1) + 1);
		
		splay(x, 0);
		splay(y, x);
		tree[tree[tree[root].r].l].lazy ^= 1;
	}
	
	write(root);
	
	return 0;
}