Splay [区间-数组模拟] 模板

#include <cstdio>
#include <algorithm>

const int N = 1e5 + 5;
int n, a[N], tot, root;

struct node {
	int v, s, c[2], fa, rev;
	node() { rev = v = fa = c[0] = c[1] = 0, s = 1; }
	node(int v, int fa) : v(v), fa(fa) { c[0] = c[1] = rev = 0; }
} tr[N];

void up(int o) {
	tr[o].s = 1;
	if (tr[o].c[0]) tr[o].s += tr[tr[o].c[0]].s;
	if (tr[o].c[1]) tr[o].s += tr[tr[o].c[1]].s;
}

void down(int o) {
	if (!tr[o].rev) return;
	if (tr[o].c[0]) tr[tr[o].c[0]].rev ^= 1;
	if (tr[o].c[1]) tr[tr[o].c[1]].rev ^= 1;
	tr[o].rev = 0;
	std::swap(tr[o].c[0], tr[o].c[1]);
}

int son(int up, int down) { return down == tr[up].c[1]; }

int build(int &o, int x[], int l, int r) {
	if (l > r) return 0;
	o = ++tot;
	if (l == r) { tr[o].v = x[l]; return o;	}
	int mid = ceil((l + r) / 2.);
	tr[o].c[0] = build(tr[o].c[0], x, l, mid - 1);
	if (tr[o].c[0]) tr[tr[o].c[0]].fa = o;
	tr[o].c[1] = build(tr[o].c[1], x, mid, r);
	if (tr[o].c[1]) tr[tr[o].c[1]].fa = o;
	up(o);
	return o;
}

void rotate(int o) {
	int f = tr[o].fa, gf = tr[f].fa;
	if (!f) return;
	int d = son(f, o), gd = 0;
	if (gf) gd = son(gf, f);
	tr[f].c[d] = tr[o].c[d ^ 1];
	if (tr[o].c[d ^ 1]) tr[tr[o].c[d ^ 1]].fa = f;
	tr[o].c[d ^ 1] = f;	tr[f].fa = o;
	gf ? tr[gf].c[gd] = o : root = o; tr[o].fa = gf;
}

int search(int o, int k) {
	down(o); int s = 0;
	if (tr[o].c[0]) s = tr[tr[o].c[0]].s;
	if (k < s + 1) return search(tr[o].c[0], k);
	else if (k > s + 1) return search(tr[o].c[1], k - (s + 1));
	else return o;
}

int at(int k) { return search(root, k); }

void splay(int o, int t) {
	while (tr[o].fa != t) {
		int f = tr[o].fa, gf = tr[f].fa;
		if (gf == t) { rotate(o); break; }
		int d = son(f, o), gd = son(gf, f);
		d == gd ? rotate(f) : rotate(o);
		rotate(o);
	}
}

int main() {
	return 0;
}
Code language: PHP (php)