Advertisement
trafik

ДД

May 18th, 2022
470
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4. #include <algorithm>
  5. #include <set>
  6. #include <chrono>
  7. #include <random>
  8. #define len(v) (int)v.size()
  9. #define all(v) v.begin(), v.end()
  10. #define rall(v) v.rbegin(), v.rend()
  11. using namespace std;
  12. const int maxn = 1e5 + 10;
  13. const int inf = 1e9;
  14. const int m = 1e9 + 7;
  15.  
  16. mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
  17.  
  18. struct Node
  19. {
  20.     int x; // Хранимый ключ
  21.     int y; // "Порядок" вершины
  22.     int sz; // Размер поддерева (количество узлов, находящихся ниже данного)
  23.     Node* l, * r; // Указатели на потомков данного узла
  24.  
  25.     // Конструктор узла (объявлен в описании самой структуры для простоты)
  26.     Node(int _x)
  27.     {
  28.         x = _x;
  29.         y = rnd() % m;
  30.         sz = 1;
  31.         l = r = nullptr;
  32.     }
  33. };
  34.  
  35. // Прототипы функций для работы с размером поддерева - их реализуем ниже.
  36. int get_sz(Node* t);
  37. void update(Node* t);
  38.  
  39. // --- Основные операции - слияние (merge) и разделение (split) деревьев
  40. // Важно! При выполнении этих операций исходные деревья могут перестать быть
  41. // валидными!
  42.  
  43. // Слияние двух деревьев (t1, t2). Работает корректно тогда и только тогда,
  44. // когда max(t1) < min(t2). Результат - корень нового дерева.
  45. Node* merge(Node* t1, Node* t2)
  46. {
  47.     // Пустое дерево - то, у которого корень - nullptr.
  48.     // Считаем, что слияние дерева с пустым деревом - это исходное дерево.
  49.     if (t1 == nullptr) { return t2; }
  50.     if (t2 == nullptr) { return t1; }
  51.  
  52.     // Дерево с большим значением y становится новым корнем
  53.     if (t1->y > t2->y)
  54.     {
  55.         // Сливаем правое поддерево первого дерева со вторым деревом и ставим
  56.         // результат в правое поддерево первого дерева.
  57.         t1->r = merge(t1->r, t2);
  58.         // Поскольку теперь дерево t1 поменялось, запускаем в нём обновление.
  59.         update(t1);
  60.         // Новый корень дерева - t1.
  61.         return t1;
  62.     }
  63.     else
  64.     {
  65.         // Сливаем всё первое дерево с левым поддеревом второго дерева
  66.         // (обязательно именно в таком порядке!!) и ставим результат в левое поддерево
  67.         // второго дерева.
  68.         t2->l = merge(t1, t2->l);
  69.         // Пересчитываем значение в новом корне дерева
  70.         update(t2);
  71.         return t2;
  72.     }
  73. }
  74.  
  75. // Разделение дерева на два по заданному ключу. После этого в первом дереве
  76. // будут значения (-inf, x), во втором - [x, +inf)
  77. void split(Node* t, int x, Node*& t1, Node*& t2)
  78. {
  79.     // Пустое дерево будет в любом случае разделено на два пустых поддерева
  80.     if (t == nullptr)
  81.     {
  82.         t1 = t2 = nullptr;
  83.         return;
  84.     }
  85.     // Если текущая вершина содержит значение, меньшее, чем заданное,
  86.     // то она отправляется в первое дерево. Правое поддерево данной вершины
  87.     // в принципе может оказаться больше или равно x, так что его тоже разрезаем,
  88.     // и записываем первое дерево-результат на его место.
  89.     if (t->x < x)
  90.     {
  91.         split(t->r, x, t->r, t2);
  92.         t1 = t;
  93.     }
  94.     else
  95.     {
  96.         // В противном случае "режем" левое поддерево. Рассуждения остаются такими
  97.         // же (текущая вершина отправляется во второе дерево-результат)
  98.         split(t->l, x, t1, t->l);
  99.         t2 = t;
  100.     }
  101.     // В процессе отрезания мы модифицируем дерево, поэтому для данной вершины надо
  102.     // пересчитать хранимое выражение
  103.     update(t);
  104. }
  105.  
  106. // Безопасное получение размера поддерева
  107. int get_sz(Node* t)
  108. {
  109.     // Размер пустых деревьев считаем равным нулю
  110.     if (t == nullptr) { return 0; }
  111.     // У непустых поддеревьев размер хранится в корне
  112.     return t->sz;
  113. }
  114.  
  115. // Обновление размера поддерева
  116. void update(Node* t)
  117. {
  118.     // Размер обновляем только для непустых деревьев
  119.     if (t != nullptr)
  120.     {
  121.         t->sz = 1 + get_sz(t->l) + get_sz(t->r);
  122.     }
  123. }
  124.  
  125.  
  126. // --- Операции, проводимые с деревом
  127.  
  128. // Добавление нового элемента x в дерево t. Корень дерева может измениться!
  129. void add(Node*& t, int x)
  130. {
  131.     Node* t1, * t2;
  132.     // Для добавления делаем следующее:
  133.     // - Разрезаем исходное дерево по ключу x. В левом поддереве все элементы меньше x,
  134.     //   в правом - не меньше.
  135.     split(t, x, t1, t2);
  136.     // - Создаём новое дерево из одной вершины - собственно, x.
  137.     Node* new_tree = new Node(x);
  138.     // - Производим слияние левого поддерева с новым, потом слияние результата с правым
  139.     //   Результат слияния - новый корень дерева.
  140.     t = merge(merge(t1, new_tree), t2);
  141. }
  142.  
  143. // Удаление вершины из дерева. В данном случае работать будет только с целыми числами!
  144. void remove(Node*& t, int x)
  145. {
  146.     Node* t1, * t2, * t3, * t4;
  147.     // Для удаления делаем следующее:
  148.     // - Разрезаем исходное дерево по ключу x.
  149.     split(t, x, t1, t2);
  150.     // - Разрезаем правое поддерево по ключу x + 1
  151.     split(t2, x + 1, t3, t4);
  152.     // - Соединяем деревья t1 и t4, которые теперь не содержат ключа x
  153.     //   (он остался в дереве t3)
  154.     t = merge(t1, t4);
  155.     // - Очищаем память, занимаемую деревом t3 (если не хотим утечек)
  156.     delete t3;
  157. }
  158.  
  159. // Вывод элементов дерева на экран в отсортированном порядке (обход ЛКП)
  160. void print(Node* t)
  161. {
  162.     // У пустых деревьев выводить нечего
  163.     if (t != nullptr)
  164.     {
  165.         // Сначала выводим всё из левого поддерева, затем то, что хранится в
  166.         // корне, затем всё из правого поддерева
  167.         print(t->l);
  168.         cout << t->x << " ";
  169.         print(t->r);
  170.     }
  171. }
  172.  
  173. // Получение элемента, стоящего на k-м месте в дереве (начиная с единицы!)
  174. int get_k(Node* t, int k)
  175. {
  176.     if (k < get_sz(t->l))
  177.     {
  178.         return get_k(t->l, k);
  179.     }
  180.     else if (k == get_sz(t->l))
  181.     {
  182.         return t->x;
  183.     }
  184.     else
  185.     {
  186.         return get_k(t->r, k - get_sz(t->l) - 1);
  187.     }
  188. }
  189.  
  190. bool find(Node* t, int k) {
  191.     if (!t)
  192.         return false;
  193.     if (t->x == k)
  194.         return true;
  195.     if (t->x > k)
  196.         return find(t->l, k);
  197.     else
  198.         return find(t->r, k);
  199. }
  200.  
  201. Node* next(Node* t, int k) {
  202.     Node *cur = t, *succ = NULL;
  203.     while (cur != NULL) {
  204.         if (cur->x > k) {
  205.             succ = cur;
  206.             cur = cur->l;
  207.         }
  208.         else
  209.             cur = cur->r;
  210.     }
  211.     return succ;
  212. }
  213.  
  214. Node* prev(Node* t, int k, int res = -1) {
  215.     Node* cur = t, * succ = NULL;
  216.     while (cur != NULL) {
  217.         if (cur->x < k) {
  218.             succ = cur;
  219.             cur = cur->r;
  220.         }
  221.         else
  222.             cur = cur->l;
  223.     }
  224.     return succ;
  225. }
  226.  
  227. void solve() {
  228.     Node* treap = nullptr;
  229.     string cmd;
  230.     while (cin >> cmd) {
  231.         int x; cin >> x;
  232.         if (cmd[0] == 'i') {
  233.             add(treap, x);
  234.         }
  235.         else if (cmd[0] == 'd') {
  236.             remove(treap, x);
  237.         }
  238.         else if (cmd[0] == 'e') {
  239.             bool res = find(treap, x);
  240.             if (res)
  241.                 cout << "true\n";
  242.             else
  243.                 cout << "false\n";
  244.         }
  245.         else if (cmd[0] == 'n') {
  246.             Node* res = next(treap, x);
  247.             if (res == NULL)
  248.                 cout << "none\n";
  249.             else
  250.                 cout << res->x << "\n";
  251.         }
  252.         else if (cmd[0] == 'p') {
  253.             Node* res = prev(treap, x);
  254.             if (res == NULL)
  255.                 cout << "none\n";
  256.             else
  257.                 cout << res->x << "\n";
  258.         }
  259.     }
  260. }  
  261.  
  262. int main() {
  263.     ios::sync_with_stdio(false);
  264.     cin.tie(nullptr);
  265.     cout.tie(nullptr);
  266.  
  267.     solve();
  268. }
Advertisement
RAW Paste Data Copied
Advertisement