Treap...

Treap.cpp

#include <cstdio>
#include <algorithm>
#include <ctime>
#include <cstdlib>

using namespace std;

struct node{
	int val, key, size;
	node* ch[2], *p;
	int getDir(){
		return p->ch[1] == this;
	}
	void update(){
		size = 1 + (ch[0]?(ch[0]->size):(0)) + (ch[1]?(ch[1]->size):(0));
	}
} mem[10000011], *top = NULL, *st = mem;

void rotate(node *cur){
	int dir = cur->getDir(); node* f = cur->p;
	cur->p = f->p;
	if (f->p) 
		f->p->ch[f->getDir()] = cur;
	f->ch[dir] = cur->ch[dir^1];
	if (cur->ch[dir^1]) cur->ch[dir^1]->p = f;
	f->p = cur;cur->ch[dir^1] = f;
	f->update();cur->update();
}

int push_up(node *cur){
	int cnt = 0;
	for (; cur->p; cnt++){
		if (cur->p->key > cur->key)
			rotate(cur);
		else
			return cnt;
	}
	return cnt;
}

int insert(int val, node * &cur, node* par){
	if (cur == NULL){
		cur = st++;cur->val = val;cur->key = rand();cur->size = 1;cur->p = par;cur->ch[0] = cur->ch[1] = NULL;
		return push_up(cur);
	}
	return insert(val, cur->ch[val > cur->val], cur);
}

const int MaxN = 10000000;

int main(){
	long long sum = 0;
	srand(time(NULL));
	freopen("t.out", "w", stdout);
	for (int i = 0; i < MaxN; i++){
		int cnt = insert(MaxN - i, top, NULL);
		sum += cnt;
	}
	printf("SUM = %d\n", sum);
	return 0;
}