赤黒木

最初に
これいる?

要はmergeとかsplitとかできるようになった強い配列です。ここらへんを参考にして実装しました。
https://www.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-day4-copypaste-slides.pdf
http://algoogle.hadrori.jp/algorithm/prbtree.html
http://algoogle.hadrori.jp/algorithm/rbtree_merge.html
http://hogloid.hatenablog.com/entry/20120407/1333788248

なんとmerge/split baseの赤黒木は平衡の仕方を2種類覚えるだけで実装できます。これは絶対Splay木とかよりも楽。zig-zagとか絶対忘れるし。さらに永続化もできて、最強感が漂っています。
でも平衡木を使う機会が競プロではほとんどなく、永続平衡木なんてcopy and pasteくらいだと思います。
大体平衡木使おうとおもってもsegtreeとかで済む場合が多いのでライブラリ化したところであまり使わなさそうです…。

template<class T>
struct rbvector { //added insert O(logn), but random access is O(logn) too
	const bool black = false;
	const bool red = true;
	struct node {
		T t;
		bool color; int rnk, sz;
		node *nl, *nr;
	};
	typedef pair<node*, node*> np;

	node *root;
	inline int size() { return !root ? 0 : root->sz; }
	inline void update(node *a) {
		if(!a->nl) { a->rnk = 0; a->sz = 1; }
		else {
			a->rnk = a->nl->rnk + (a->nl->color == black);
			a->sz = a->nl->sz + a->nr->sz;
		}
	}
	node *new_node(bool color, T t, node *nl = NULL, node *nr = NULL) {
		node *nn = new node();
		nn->nl = nl; nn->nr = nr; nn->color = color; nn->t = t;
		update(nn);
		return nn;
	}
	node *merge_sub(node *a, node *b) {
		if(a->rnk < b->rnk) {
			node *c = merge_sub(a, b->nl);
			b->nl = c;
			if(b->color == black && c->color == red && c->nl->color == red) {
				if(b->nr->color == black) {
					node *y = c->nr;
					c->nr = b; b->nl = y;
					b->color = red; c->color = black;
					update(b); update(c);
					return c;
				}
				else {
					b->color = red;
					c->color = b->nr->color = black;
					update(c); update(b);
					return b;
				}
			}
			else { update(b); return b; };
		}
		else if(a->rnk > b->rnk) {
			node *c = merge_sub(a->nr, b);
			a->nr = c;
			if(a->color == black && c->color == red && c->nr->color == red) {
				if(a->nl->color == black) {
					node *y = c->nl;
					c->nl = a; a->nr = y;
					a->color = red; c->color = black;
					update(a); update(c);
					return c;
				}
				else {
					a->color = red;
					c->color = a->nl->color = black;
					update(c); update(a);
					return a;
				}
			}
			else { update(a); return a; }
		}
		else {
			node *c = new_node(red, T(), a, b);
			return c;
		}
	}
	node *merge(node *a, node *b) {
		if(!a) return b;
		if(!b) return a;
		a->color = black; update(a);
		b->color = black; update(b);
		node *c = merge_sub(a, b);
		c->color = black;
		return c;
	}
	np split(node *v, int k) {
		if(k <= 0) return np(NULL, v);
		if(k >= v->sz) return np(v, NULL);
		if(k < v->nl->sz) {
			np p = split(v->nl, k);
			return np(p.fst, merge(p.sec, v->nr));
		}
		else if(k > v->nl->sz) {
			np p = split(v->nr, k - v->nl->sz);
			return np(merge(v->nl, p.fst), p.sec);
		}
		else return np(v->nl, v->nr);
	}

	T& get_sub(node *a, int k, int l, int r) {
		if(r - l == 1) return a->t;
		if(k < a->nl->sz) return get_sub(a->nl, k, l, l + a->nl->sz);
		else return get_sub(a->nr, k - a->nl->sz, l + a->nl->sz, r);
	}
	void insert(const rbvector& sa, int k) { //after insert, sa is broken
		np p = split(root, k);
		root = merge(merge(p.fst, sa.root), p.sec);
	}
	void insert(T t, int k) {
		np p = split(root, k);
		root = merge(merge(p.fst, new_node(black, t)), p.sec);
	}
	T& get(int k) { return get_sub(root, k, 0, size()); }
	T& operator[](int k) { return get(k); }
	void push_back(const rbvector& sa) { insert(sa, size()); }
	void push_back(T t) { insert(t, size()); }

	friend ostream& operator<<(ostream& out, rbvector& sa){
		out << "[";
		rep(i, 0, sa.size() - 1) {
			out << sa.get(i) << ", ";
		}
		out << sa.get(sa.size() - 1) << "]";
		return out;
	}
};

mergeを見るとこうなっています。

node *merge(node *a, node *b) {
	if(!a) return b;
	if(!b) return a;
	a->color = black; update(a);
	b->color = black; update(b);
	node *c = merge_sub(a, b);
	c->color = black;
	return c;
}

上のhosさんのスライドと比べてa->color = blackという行が追加されています。それはなぜかというとsplitから根が赤色の木が出てくる可能性があるからです。
根を赤→黒にしてもrankに影響は出ないので、mergeするとき、2つの木の根を黒色にしてから処理するようにしています。

ちなみに永続化のコードはもっとシンプルになってえぇ…と困惑するかもしれませんが、めんどくさい処理をnew_nodeに押し付けられるからですね。

完全永続データ構造をマージする一般的なテクニック系Union Findを実装しようと思って永続配列を作ろう!ってなったんですが、そもそもそんなUF作ったところで使うところがないことに気づいて虚無です。