Расширения декартова дерева - История изменений

Ctrlalt в 15:09, 24 мая 2023

2023-05-24T15:09:39Z

← Предыдущая версия		Версия от 15:09, 24 мая 2023
Строка 1:		Строка 1:
			== TLDR ==
			<youtube width="300" height="180">MLIbII4sBs0</youtube>
			<youtube width="300" height="180">mkpeHhmmUPw</youtube>

	== Multimap с getMinValue ==		== Multimap с getMinValue ==
	{\|width=100%		{\|width=100%

Ctrlalt: /* Multimap с getMinValue */

2023-04-29T15:12:32Z

Multimap с getMinValue

← Предыдущая версия		Версия от 15:12, 29 апреля 2023
Строка 13:		Строка 13:

	int getMinValue(Node *n) const {		int getMinValue(Node *n) const {
	return n ? n->minValue : ~~1e9~~;		return n ? n->minValue : 2e9;
	}		}

Строка 99:		Строка 99:

	int getMinValue(Node *n) const {		int getMinValue(Node *n) const {
	return n ? n->minValue : ~~1e9~~;		return n ? n->minValue : 2e9;
	}		}

Ctrlalt: /* Vector */

2023-04-29T15:12:06Z

Vector

← Предыдущая версия		Версия от 15:12, 29 апреля 2023
Строка 509:		Строка 509:

	int getMinValue(Node *n) {		int getMinValue(Node *n) {
	return n ? n->minValue : ~~1e9~~;		return n ? n->minValue : 2e9;
	}		}

Ctrlalt в 22:14, 9 декабря 2022

2022-12-09T22:14:54Z

Внесённые изменения

Ctrlalt в 21:55, 9 декабря 2022

2022-12-09T21:55:30Z

Внесённые изменения

Ctrlalt в 19:13, 21 декабря 2021

2021-12-21T19:13:52Z

@@ Строка 178: / Строка 178: @@
           split(b, r - l + 1, b, c);
           int res = getMaxV(b);
           root = merge(a, merge(b, c));
           return res;

Ctrlalt: /* Ссылки */

2020-08-21T05:19:23Z

Ссылки

← Предыдущая версия		Версия от 05:19, 21 августа 2020
Строка 185:		Строка 185:
	== Ссылки ==		== Ссылки ==
	Теория:		Теория:
			* [https://www.youtube.com/watch?v=MLIbII4sBs0&list=PLGhUJWLZ8uQ5Ewplzb1ER29p4-kQme5Yr&index=5 Фолунин В. — Декартово дерево по неявному ключу]
	* [http://e-maxx.ru/algo/treap#7 e-maxx.ru — Неявные декартовы деревья]		* [http://e-maxx.ru/algo/treap#7 e-maxx.ru — Неявные декартовы деревья]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE_%D0%BD%D0%B5%D1%8F%D0%B2%D0%BD%D0%BE%D0%BC%D1%83_%D0%BA%D0%BB%D1%8E%D1%87%D1%83 neerc.ifmo.ru/wiki — Декартово дерево по неявному ключу]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE_%D0%BD%D0%B5%D1%8F%D0%B2%D0%BD%D0%BE%D0%BC%D1%83_%D0%BA%D0%BB%D1%8E%D1%87%D1%83 neerc.ifmo.ru/wiki — Декартово дерево по неявному ключу]
Строка 190:		Строка 191:
	* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/zksh_cartesian.pdf Иващенко Д., Семенов К. Декартово дерево]		* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/zksh_cartesian.pdf Иващенко Д., Семенов К. Декартово дерево]
	Код:		Код:
	* [~~http~~://github.com/indy256/codelibrary/blob/master/~~java~~/~~src~~/~~TreapImplicitKey~~.~~java CodeLibrary — Treap with implicit key with interval modification~~]		* [https://github.com/indy256/codelibrary/blob/master/cpp/structures/treap_indexed.cpp github.com/indy256/codelibrary/blob/master/cpp/structures/treap_indexed.cpp]
	* [http://github.com/ADJA/algos/blob/master/DataStructures/CartesianTreeImplicitKeys.cpp Algos — Cartesian tree using implicit keys]		* [http://github.com/ADJA/algos/blob/master/DataStructures/CartesianTreeImplicitKeys.cpp Algos — Cartesian tree using implicit keys]
	Задачи:		Задачи:

Ctrlalt в 13:51, 23 сентября 2019

2019-09-23T13:51:39Z

← Предыдущая версия		Версия от 13:51, 23 сентября 2019
Строка 1:		Строка 1:
	[http://codeforces.com/contest/61/submission/~~61118716~~ pbds]		[http://codeforces.com/contest/61/submission/61118877 pbds]

	minstd_rand gen;		minstd_rand gen;

Ctrlalt в 13:46, 23 сентября 2019

2019-09-23T13:46:08Z

← Предыдущая версия		Версия от 13:46, 23 сентября 2019
Строка 1:		Строка 1:
			[http://codeforces.com/contest/61/submission/61118716 pbds]

	minstd_rand gen;		minstd_rand gen;

Ctrlalt в 01:20, 3 августа 2019

2019-08-03T01:20:36Z

← Предыдущая версия		Версия от 01:20, 3 августа 2019
Строка 1:		Строка 1:
			minstd_rand gen;

			class Treap {
			struct Node {
			int key, priority, nodeSize, subtreeSize;
			Node left, right;
			Node(int key) : key(key), priority(gen()), nodeSize(1), subtreeSize(1), left(0), right(0) {}
			} *root;
			int getSubtreeSize(Node *n) const {
			return n ? n->subtreeSize : 0;
			}
			void update(Node *n) {
			if (n) {
			n->subtreeSize = getSubtreeSize(n->left) + n->nodeSize + getSubtreeSize(n->right);
			}
			}
			Node merge(Node a, Node *b) {
			if (!a \|\| !b) {
			return a ? a : b;
			}
			if (a->priority > b->priority) {
			a->right = merge(a->right, b);
			update(a);
			return a;
			} else {
			b->left = merge(a, b->left);
			update(b);
			return b;
			}
			}
			void split(Node t, int key, Node &a, Node *&b) {
			if (!t) {
			a = b = 0;
			return;
			}
			if (t->key < key) {
			split(t->right, key, t->right, b);
			a = t;
			} else {
			split(t->left, key, a, t->left);
			b = t;
			}
			update(a);
			update(b);
			}
			int indexOf(Node *n, int key) const {
			if (!n) {
			return 0;
			} else if (n->key < key) {
			return getSubtreeSize(n->left) + n->nodeSize + indexOf(n->right, key);
			} else if (n->key == key) {
			return getSubtreeSize(n->left);
			} else {
			return indexOf(n->left, key);
			}
			}
			int getByIndex(Node *n, int index) const {
			int leftSize = getSubtreeSize(n->left);
			if (leftSize > index) {
			return getByIndex(n->left, index);
			} else if (leftSize + n->nodeSize < index) {
			return getByIndex(n->right, index - leftSize - n->nodeSize);
			} else {
			return n->key;
			}
			}
			public:
			Treap() : root(0) {}
			int size() const {
			return getSubtreeSize(root);
			}
			int indexOf(int key) const {
			return indexOf(root, key);
			}
			int operator [] (int index) const {
			return getByIndex(root, index);
			}
			void insert(int key) {
			Node less, equal, *greater;
			split(root, key, less, equal);
			split(equal, key + 1, equal, greater);
			if (equal) {
			equal->nodeSize++;
			equal->subtreeSize++;
			} else {
			equal = new Node(key);
			}
			equal = merge(equal, greater);
			root = merge(less, equal);
			}
			void erase(int key) {
			Node less, equal, *greater;
			split(root, key, less, equal);
			split(equal, key + 1, equal, greater);
			root = merge(less, greater);
			}
			void eraseOne(int key) {
			Node less, equal, *greater;
			split(root, key, less, equal);
			split(equal, key + 1, equal, greater);
			if (equal) {
			equal->nodeSize--;
			equal->subtreeSize--;
			if (!equal->nodeSize) {
			equal = 0;
			}
			}
			equal = merge(equal, greater);
			root = merge(less, equal);
			}
			};



	struct TN {		struct TN {
	int v, p, c, maxV;		int v, p, c, maxV;