From 22536b7fbc050075a1420c0f1a7125b9185c9519 Mon Sep 17 00:00:00 2001
From: Yidi <noob999noob999@gmail.com>
Date: Mon, 12 Aug 2024 13:22:34 +0200
Subject: add treap test

---
 content/datastructures/treap.cpp | 140 +++++++++++++++++++--------------------
 1 file changed, 70 insertions(+), 70 deletions(-)

(limited to 'content/datastructures/treap.cpp')

diff --git a/content/datastructures/treap.cpp b/content/datastructures/treap.cpp
index c96e36a..c5a60e9 100644
--- a/content/datastructures/treap.cpp
+++ b/content/datastructures/treap.cpp
@@ -1,79 +1,79 @@
-struct node {
-	int key, prio, left, right, size;
-	node(int key, int prio) : key(key), prio(prio), left(-1),
-	                          right(-1), size(1) {};
-};
+mt19937 rng(0xc4bd5dad);
+struct Treap {
+	struct Node {
+		ll val;
+		int prio, size = 1, l = -1, r = -1;
+		Node(ll x) : val(x), prio(rng()) {}
+	};
 
-vector<node> treap;
+	vector<Node> treap;
+	int root = -1;
 
-int getSize(int root) {
-	return root < 0 ? 0 : treap[root].size;
-}
+	int getSize(int v) {
+		return v < 0 ? 0 : treap[v].size;
+	}
 
-void update(int root) {
-	if (root < 0) return;
-	treap[root].size = 1 + getSize(treap[root].left)
-	                     + getSize(treap[root].right);
-}
+	void upd(int v) {
+		if (v < 0) return;
+		auto& V = treap[v];
+		V.size = 1 + getSize(V.l) + getSize(V.r);
+		// Update Node Code
+	}
 
-pair<int, int> split(int root, int minKeyRight) {
-	if (root < 0) return {-1, -1};
-	if (treap[root].key >= minKeyRight) {
-		auto leftSplit = split(treap[root].left, minKeyRight);
-		treap[root].left = leftSplit.second;
-		update(root);
-		leftSplit.second = root;
-		return leftSplit;
-	} else {
-		auto rightSplit = split(treap[root].right, minKeyRight);
-		treap[root].right = rightSplit.first;
-		update(root);
-		rightSplit.first = root;
-		return rightSplit;
-}}
+	void push(int v) {
+		if (v < 0) return;
+		//auto& V = treap[v];
+		//if (V.lazy) {
+		//	Lazy Propagation Code
+		//	if (V.l >= 0) treap[V.l].lazy = true;
+		//	if (V.r >= 0) treap[V.r].lazy = true;
+		//	V.lazy = false;
+		//}
+	}
 
-int merge (int left, int right) {
-	if (left < 0) return right;
-	if (right < 0) return left;
-	if (treap[left].prio < treap[right].prio) { //min priority heap
-		treap[left].right = merge(treap[left].right, right);
-		update(left);
-		return left;
-	} else {
-		treap[right].left = merge(left, treap[right].left);
-		update(right);
-		return right;
-}}
+	pair<int, int> split(int v, int k) {
+		if (v < 0) return {-1, -1};
+		auto& V = treap[v];
+		push(v);
+		if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k)
+			auto [left, right] = split(V.l, k);
+			V.l = right;
+			upd(v);
+			return {left, v};
+		} else {
+			// and only "k"
+			auto [left, right] = split(V.r, k - getSize(V.l) - 1);
+			V.r = left;
+			upd(v);
+			return {v, right};
+	}}
 
-//insert values with high priority first
-int insert(int root, int key, int prio) {
-	int next = sz(treap);
-	treap.emplace_back(key, prio);
-	auto t = split(root, key);
-	//returns new root
-	return merge(merge(t.first, next), t.second);
-}
+	int merge(int left, int right) {
+		if (left < 0) return right;
+		if (right < 0) return left;
+		if (treap[left].prio < treap[right].prio) {
+			push(left);
+			treap[left].r = merge(treap[left].r, right);
+			upd(left);
+			return left;
+		} else {
+			push(right);
+			treap[right].l = merge(left, treap[right].l);
+			upd(right);
+			return right;
+	}}
 
-int remove(int root, int key) {
-	if (root < 0) return -1;
-	if (key < treap[root].key) {
-		treap[root].left = remove(treap[root].left, key);
-		update(root);
-		return root;
-	} else if (key > treap[root].key) {
-		treap[root].right = remove(treap[root].right, key);
-		update(root);
-		return root;
-	} else { //check prio?
-		return merge(treap[root].left, treap[root].right);
-}}
+	void insert(int i, ll val) { // and i = val
+		auto [left, right] = split(root, i);
+		treap.emplace_back(val);
+		left = merge(left, sz(treap) - 1);
+		root = merge(left, right);
+	}
 
-int kth(int root, int k) {
-	if (root < 0) return -1;
-	int leftSize = getSize(treap[root].left);
-	if (k < leftSize) return kth(treap[root].left, k);
-	else if (k > leftSize) {
-		return kth(treap[root].right, k - 1 - leftSize);
+	void remove(int i, int count = 1) {
+		auto [left, t_right] = split(root, i);
+		auto [middle, right] = split(t_right, count);
+		root = merge(left, right);
 	}
-	return root;
-}
+	// for query use remove and read middle BEFORE remerging
+};
-- 
cgit v1.2.3