Treap.cpp

/**

   * author:    Diego Briaares
   * At:   25.07.2022 01:52:27
**/

#include <bits/stdc++.h>
using namespace std;

void optimize() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

// Randal

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node {
	node* L;
	node* R;
	int key, pry;
	int sz;
};

const int MAXNODES = 200002;
node treap[MAXNODES];
int nodes;

int size(node* T) {
	if (T == NULL) {
		return 0;
	}
	return T->sz;
}

void Merge(node* &T, node* A, node* B) {
	if (A == NULL) {
		T = B;
		return;
	}
	if (B == NULL) {
		T = A;
		return;
	}

	if (A->pry >= B->pry) {
		Merge(A->R, A->R, B);
		T = A;
	}
	else {
		Merge(B->L, A, B->L);
		T = B;
	}
	T->sz = (size(T->L) + size(T->R) + 1);
	return;
}

void Split(node* T, int k, node* &A, node* &B) {
	if (T == NULL) {
		A = B = NULL;
		return;
	}
	if (T->key > k) {
		Split(T->L, k, A, T->L);
		B = T;
		B->sz = (size(B->L) + size(B->R) + 1);
	}
	else {
		Split(T->R, k, T->R, B);
		A = T;
		A->sz = (size(A->L) + size(A->R) + 1);
	}
	return;
}

node* new_node(int v = 0) {
	if (nodes >= MAXNODES) {
		cout << "NEL PASTEL (muchos nodos)\n";
		return NULL;
	}
	node* NewT = &treap[nodes++];
	NewT->sz = 1;
	NewT->L = NULL;
	NewT->R = NULL;
	NewT->key = v;
	NewT->pry = uniform_int_distribution<int>(0, MAXNODES * 10)(rng);
	return NewT; 
}

bool Find(node* T, int v) {
	if (T == NULL) {
		return false;
	}
	else if (T->key == v) {
		return true;
	}
	else if (T->key < v) {
		return Find(T->R, v);
	}
	else {
		return Find(T->L, v);
	}
}

/* - */
vector<int> inorder(node* T) {
	if (T == NULL) {
		return vector<int>();
	}
	vector<int> order;
	vector<int> L = inorder(T->L);
	order.insert(order.end(), L.begin(), L.end());
	order.push_back(T->key);
	vector<int> R = inorder(T->R);
	order.insert(order.end(), R.begin(), R.end());
	return order;
} /* -- */


// No debe haber un v
void Insert(node* &T, int v = 0) {
	node* T1;
	node* T2;
	Split(T, v, T1, T2);
	Merge(T1, T1, new_node(v));
	Merge(T, T1, T2);
	return;
}


// Debe haber un v 
void Erase(node* &T, int v) {
	node* T1;
	node* T2;
	node* T3;
	Split(T, v, T1, T2);
	Split(T1, v - 1, T1, T3);
	Merge(T, T1, T2);
	return;
}


// Debe haber un k-esimo elemento
int OrdK(node* &T, int k) {
	if (T == NULL) {
		return 420;
	}
	if (size(T->L) + 1 == k) {
		return T->key;
	}
	if (size(T->L)  + 1 < k) {
		return OrdK(T->R, k - size(T->L) - 1);
	}
	else {
		return OrdK(T->L, k);
	}
}

int Count(node* &T, int x) {
	if (T == NULL) {
		return 0;
	}
	node* T1;
	node* T2;
	Split(T, x, T1, T2);
	int amt = size(T1);
	Merge(T, T1, T2);
	return amt;
}


	int main () {
		optimize();
		
	}