Расширения декартова дерева: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показано 7 промежуточных версий этого же участника)
Строка 1: Строка 1:
[http://codeforces.com/contest/61/submission/61118716 pbds]
== TLDR ==
<youtube width="300" height="180">MLIbII4sBs0</youtube>
<youtube width="300" height="180">mkpeHhmmUPw</youtube>


  minstd_rand gen;
== Multimap с getMinValue ==
{|width=100%
|width=50%|
'''getMinValue(lKey, rKey)'''
  class Treap {
    inline static minstd_rand gen;
    struct Node {
        int key, priority, value, minValue;
        Node *left = 0, *right = 0;
        Node(int key, int value) : key(key), priority(gen()), value(value), minValue(value) {}
    } *root = 0;
    int getMinValue(Node *n) const {
        return n ? n->minValue : 2e9;
    }
    void update(Node *n) {
        if (n)
            n->minValue = min({ getMinValue(n->left), n->value, getMinValue(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);
    }
public:
    void insert(int key, int value) {
        Node *a, *b;
        split(root, key, a, b);
        root = merge(a, merge(new Node(key, value), b));
    }
    void erase(int key) {
        Node *a, *b, *c;
        split(root, key, a, b);
        split(b, key + 1, b, c);
        root = merge(a, c);
    }
    void eraseOne(int key) {
        Node *a, *b, *c;
        split(root, key, a, b);
        split(b, key + 1, b, c);
        if (b)
            b = merge(b->left, b->right);
        root = merge(a, merge(b, c));
    }
    int getMinValue(int lKey, int rKey) {
        Node *a, *b, *c;
        split(root, lKey, a, b);
        split(b, rKey + 1, b, c);
        int res = getMinValue(b);
        root = merge(a, merge(b, c));
        return res;
    }
};
|width=50%|
'''getMinValue(lIndex, rIndex)'''
  class Treap {
  class Treap {
    inline static minstd_rand gen;
     struct Node {
     struct Node {
         int key, priority, nodeSize, subtreeSize;
         int key, priority, size = 1, value, minValue;
         Node *left, *right;
         Node *left = 0, *right = 0;
         Node(int key) : key(key), priority(gen()), nodeSize(1), subtreeSize(1), left(0), right(0) {}
         Node(int key, int value) : key(key), priority(gen()), value(value), minValue(value) {}
     } *root;
     } *root = 0;
     int getSubtreeSize(Node *n) const {
         return n ? n->subtreeSize : 0;
     int getSize(Node *n) const {
         return n ? n->size : 0;
    }
    int getMinValue(Node *n) const {
        return n ? n->minValue : 2e9;
     }
     }
     void update(Node *n) {
     void update(Node *n) {
         if (n) {
         if (n) {
             n->subtreeSize = getSubtreeSize(n->left) + n->nodeSize + getSubtreeSize(n->right);
             n->size = getSize(n->left) + 1 + getSize(n->right);
            n->minValue = min({ getMinValue(n->left), n->value, getMinValue(n->right) });
         }
         }
     }
     }
     Node *merge(Node *a, Node *b) {
     Node *merge(Node *a, Node *b) {
         if (!a || !b) {
         if (!a || !b)
             return a ? 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);
    }
    void splitByIndex(Node *t, int index, Node *&a, Node *&b) {
        if (!t) {
            a = b = 0;
            return;
        }
        int leftSize = getSize(t->left);
        if (leftSize < index) {
            splitByIndex(t->right, index - leftSize - 1, t->right, b);
            a = t;
        } else {
            splitByIndex(t->left, index, a, t->left);
            b = t;           
        }
        update(a);
        update(b);
    }
public:
    void insert(int key, int value) {
        Node *a, *b;
        split(root, key, a, b);
        root = merge(a, merge(new Node(key, value), b));
    }
    void erase(int key) {
        Node *a, *b, *c;
        split(root, key, a, b);
        split(b, key + 1, b, c);
        root = merge(a, c);
    }
    void eraseOne(int key) {
        Node *a, *b, *c;
        split(root, key, a, b);
        split(b, key + 1, b, c);
        if (b)
            b = merge(b->left, b->right);
        root = merge(a, merge(b, c));
    }
    int getMinValue(int lIndex, int rIndex) {
        Node *a, *b, *c;
        splitByIndex(root, lIndex, a, b);
        splitByIndex(b, rIndex - lIndex + 1, b, c);
        int res = getMinValue(b);
        root = merge(a, merge(b, c));
        return res;
    }
};
|}
== Multiset с indexOf(key), operator[], lessCount(key), greaterCount(key) ==
{|width=100%
|width=50%|
'''Одинаковые элементы хранятся в нескольких узлах'''
class Treap {
    inline static minstd_rand gen;
    struct Node {
        int key, priority, size = 1;
        Node *left = 0, *right = 0;
        Node(int key) : key(key), priority(gen()) {}
    } *root = 0;
    int getSize(Node *n) const {
        return n ? n->size : 0;
    }
    void update(Node *n) {
        if (n)
            n->size = getSize(n->left) + 1 + getSize(n->right);
    }
    Node *merge(Node *a, Node *b) {
        if (!a || !b)
            return a ? a : b;
         if (a->priority > b->priority) {
         if (a->priority > b->priority) {
             a->right = merge(a->right, b);
             a->right = merge(a->right, b);
Строка 31: Строка 229:
         }
         }
     }
     }
     void split(Node *t, int key, Node *&a, Node *&b) {
     void split(Node *t, int key, Node *&a, Node *&b) {
         if (!t) {
         if (!t) {
Строка 46: Строка 245:
         update(b);
         update(b);
     }
     }
     int indexOf(Node *n, int key) const {
     int indexOf(Node *n, int key) const {
         if (!n) {
         if (!n)
             return 0;
             return 0;
         } else if (n->key < key) {
         else if (key < n->key)
             return getSubtreeSize(n->left) + n->nodeSize + indexOf(n->right, key);
            return indexOf(n->left, key);
         } else if (n->key == key) {
        else if (n->key == key)
             return getSubtreeSize(n->left);
             return getSize(n->left);
        else
            return getSize(n->left) + 1 + indexOf(n->right, key);
    }
    int getByIndex(Node *n, int index) const {
        int leftSize = getSize(n->left);
        if (leftSize > index)
            return getByIndex(n->left, index);
         else if (leftSize == index)
            return n->key;
        else
            return getByIndex(n->right, index - leftSize - 1);
    }
public:
    int size() const {
        return getSize(root);
    }
    int indexOf(int key) const {
        return indexOf(root, key);
    }
    int operator[](int index) const {
        return getByIndex(root, index);
    }
    void insert(int key) {
        Node *a, *b;
        split(root, key, a, b);
        root = merge(a, merge(new Node(key), b));
    }
    void erase(int key) {
        Node *a, *b, *c;
        split(root, key, a, b);
        split(b, key + 1, b, c);
        root = merge(a, c);
    }
    void eraseOne(int key) {
        Node *a, *b, *c;
        split(root, key, a, b);
        split(b, key + 1, b, c);
        if (b)
             b = merge(b->left, b->right);
        root = merge(a, merge(b, c));
    }
    int lessCount(int key) {
        Node *a, *b;
        split(root, key, a, b);
        int res = getSize(a);
        root = merge(a, b);
        return res;
    }
    int lessEqualCount(int key) {
        Node *a, *b;
        split(root, key + 1, a, b);
        int res = getSize(a);
        root = merge(a, b);
        return res;
    }
    int greaterCount(int key) {
        Node *a, *b;
        split(root, key + 1, a, b);
        int res = getSize(b);
        root = merge(a, b);
        return res;
    }
    int greaterEqualCount(int key) {
        Node *a, *b;
        split(root, key, a, b);
        int res = getSize(b);
        root = merge(a, b);
        return res;
    }
};
|width=50%|
'''Одинаковые элементы хранятся в одном узле'''
class Treap {
    inline static minstd_rand gen;
    struct Node {
        int key, priority, nodeSize = 1, subtreeSize = 1;
        Node *left = 0, *right = 0;
        Node(int key) : key(key), priority(gen()) {}
    } *root = 0;
    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 {
         } 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 (key < n->key)
             return indexOf(n->left, key);
             return indexOf(n->left, key);
         }
         else if (n->key == key)
            return getSubtreeSize(n->left);
        else
            return getSubtreeSize(n->left) + n->nodeSize + indexOf(n->right, key);
     }
     }
     int getByIndex(Node *n, int index) const {
     int getByIndex(Node *n, int index) const {
         int leftSize = getSubtreeSize(n->left);
         int leftSize = getSubtreeSize(n->left);
         if (leftSize > index) {
         if (leftSize > index)
             return getByIndex(n->left, index);
             return getByIndex(n->left, index);
         } else if (leftSize + n->nodeSize < index) {
         else if (leftSize + n->nodeSize >= index)
            return n->key;
        else
             return getByIndex(n->right, index - leftSize - n->nodeSize);
             return getByIndex(n->right, index - leftSize - n->nodeSize);
        } else {
            return n->key;
        }
     }
     }
  public:
  public:
    Treap() : root(0) {}
     int size() const {
     int size() const {
         return getSubtreeSize(root);
         return getSubtreeSize(root);
     }
     }
     int indexOf(int key) const {
     int indexOf(int key) const {
         return indexOf(root, key);
         return indexOf(root, key);
     }
     }
     int operator [] (int index) const {
     int operator[](int index) const {
         return getByIndex(root, index);
         return getByIndex(root, index);
     }
     }
     void insert(int key) {
     void insert(int key) {
         Node *less, *equal, *greater;
         Node *a, *b, *c;
         split(root, key, less, equal);
         split(root, key, a, b);
         split(equal, key + 1, equal, greater);
         split(b, key + 1, b, c);
         if (equal) {
         if (b) {
             equal->nodeSize++;
             b->nodeSize++;
             equal->subtreeSize++;
             b->subtreeSize++;
         } else {
         } else {
             equal = new Node(key);
             b = new Node(key);
         }
         }
         equal = merge(equal, greater);
         root = merge(a, merge(b, c));
        root = merge(less, equal);
     }
     }
     void erase(int key) {
     void erase(int key) {
         Node *less, *equal, *greater;
         Node *a, *b, *c;
         split(root, key, less, equal);
         split(root, key, a, b);
         split(equal, key + 1, equal, greater);
         split(b, key + 1, b, c);
         root = merge(less, greater);
         root = merge(a, c);
     }
     }
     void eraseOne(int key) {
     void eraseOne(int key) {
         Node *less, *equal, *greater;
         Node *a, *b, *c;
         split(root, key, less, equal);
         split(root, key, a, b);
         split(equal, key + 1, equal, greater);
         split(b, key + 1, b, c);
         if (equal) {
         if (b) {
             equal->nodeSize--;
             b->nodeSize--;
             equal->subtreeSize--;
             b->subtreeSize--;
             if (!equal->nodeSize) {
             if (!b->nodeSize)
                 equal = 0;
                 b = 0;
            }
         }
         }
         equal = merge(equal, greater);
         root = merge(a, merge(b, c));
         root = merge(less, equal);
    }
    int lessCount(int key) {
        Node *a, *b;
        split(root, key, a, b);
        int res = getSize(a);
        root = merge(a, b);
        return res;
    }
    int lessEqualCount(int key) {
        Node *a, *b;
        split(root, key + 1, a, b);
        int res = getSize(a);
        root = merge(a, b);
        return res;
    }
    int greaterCount(int key) {
        Node *a, *b;
        split(root, key + 1, a, b);
        int res = getSize(b);
        root = merge(a, b);
        return res;
    }
    int greaterEqualCount(int key) {
        Node *a, *b;
        split(root, key, a, b);
        int res = getSize(b);
         root = merge(a, b);
        return res;
     }
     }
  };
  };
|}


== Set с find_by_order(index) и order_of_key(key) через __gnu_pbds ==
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;


* [http://codeforces.com/contest/61/submission/61118877 Пример решения]
* [https://codeforces.com/blog/entry/11080 Codeforces — C++ STL: Policy based data structures]


  struct TN {
 
     int v, p, c, maxV;
== Vector ==
     TN *l, *r;
{|width=100%
     TN(int V) : v(V), p(rand()), c(1), maxV(V), l(0), r(0) {}
|width=50%|
'''getMinValue(lIndex, rIndex)'''
  class ImplicitTreap {
    inline static minstd_rand gen;
    struct Node {
        int value, priority, size = 1, minValue;
        Node *left = 0, *right = 0;
        Node(int value) : value(value), priority(gen()), minValue(value) {}
    } *root = 0;
    int getSize(Node *n) {
        return n ? n->size : 0;
    }
     int getMinValue(Node *n) {
        return n ? n->minValue : 2e9;
    }
    void update(Node *n) {
        if (n) {
            n->size = getSize(n->left) + 1 + getSize(n->right);
            n->minValue = min({ getMinValue(n->left), n->value, getMinValue(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 k, Node *&a, Node *&b) {
        if (!t) {
            a = b = 0;
            return;
        }
        if (getSize(t->left) < k) {
            split(t->right, k - getSize(t->left) - 1, t->right, b);
            a = t;
        } else {
            split(t->left, k, a, t->left);
            b = t;
        }
        update(a);
        update(b);
    }
public:
    void pushBack(int value) {
        root = merge(root, new Node(value));
    }
    void pushFront(int value) {
        root = merge(new Node(value), root);
    }
    void insertAfter(int index, int value) {
        Node *a, *b;
        split(root, index, a, b);
        root = merge(a, merge(new Node(value), b));
    }
    void erase(int index) {
        Node *a, *b, *c;
        split(root, index, a, b);
        split(b, 1, b, c);
        root = merge(a, c);
    }
     void erase(int lIndex, int rIndex) {
        Node *a, *b, *c;
        split(root, lIndex, a, b);
        split(b, rIndex - lIndex + 1, b, c);
        root = merge(a, c);
    }
     int operator[](int index) {
        Node *a, *b, *c;
        split(root, index, a, b);
        split(b, 1, b, c);
        int res = b->value;
        root = merge(a, merge(b, c));
        return res;
    }
    void moveToFront(int lIndex, int rIndex) {
        Node *a, *b, *c;
        split(root, lIndex, a, b);
        split(b, rIndex - lIndex + 1, b, c);
        root = merge(b, merge(a, c));
    }
    void moveToBack(int lIndex, int rIndex) {
        Node *a, *b, *c;
        split(root, lIndex, a, b);
        split(b, rIndex - lIndex + 1, b, c);
        root = merge(a, merge(c, b));
    }
    int getMinValue(int lIndex, int rIndex) {
        Node *a, *b, *c;
        split(root, lIndex, a, b);
        split(b, rIndex - lIndex + 1, b, c);
        int res = getMinValue(b);
        root = merge(a, merge(b, c));
        return res;
    }
  };
  };
 
|width=50%|
  class ITreap {
'''reverse(lIndex, rIndex)'''
     TN *root;
  class ImplicitTreap {
     int getMaxV(TN *n) {
    inline static minstd_rand gen;
         return n ? n->maxV : -(1 << 30);
    struct Node {
        int value, priority, size = 1, rev = 0;
        Node *left = 0, *right = 0;
        Node(int value) : value(value), priority(gen()) {}
     } *root = 0;
     int getSize(Node *n) {
         return n ? n->size : 0;
     }
     }
     int getC(TN *n) {
         return n ? n->c : 0;
     void push(Node *n) {
         if (n && n->rev) {
            swap(n->left, n->right);
            if (n->left)
                n->left->rev ^= 1;
            if (n->right)
                n->right->rev ^= 1;
            n->rev = 0;
        }
     }
     }
     void update(TN *n) {
         if (!n)
     void update(Node *n) {
             return;
         if (n)
        n->c = 1 + getC(n->l) + getC(n->r);
             n->size = getSize(n->left) + 1 + getSize(n->right);
        n->maxV = max(n->v, max(getMaxV(n->l), getMaxV(n->r)));
     }
     }
     TN *merge(TN *a, TN *b) {
     Node *merge(Node *a, Node *b) {
        push(a);
        push(b);
         if (!a || !b)
         if (!a || !b)
             return a ? a : b;
             return a ? a : b;
         if (a->p > b->p) {
         if (a->priority > b->priority) {
             a->r = merge(a->r, b);
             a->right = merge(a->right, b);
             update(a);
             update(a);
             return a;
             return a;
         } else {
         } else {
             b->l = merge(a, b->l);
             b->left = merge(a, b->left);
             update(b);
             update(b);
             return b;
             return b;
         }
         }
     }
     }
     void split(TN *t, int k, TN *&a, TN *&b) {
     void split(Node *t, int k, Node *&a, Node *&b) {
        push(t);
         if (!t) {
         if (!t) {
             a = b = 0;
             a = b = 0;
             return;
             return;
         }
         }
         if (getC(t->l) < k) {
         if (getSize(t->left) < k) {
             split(t->r, k - getC(t->l) - 1, t->r, b);
             split(t->right, k - getSize(t->left) - 1, t->right, b);
             a = t;            
             a = t;
         } else {
         } else {
             split(t->l, k, a, t->l);
             split(t->left, k, a, t->left);
             b = t;  
             b = t;
         }
         }
         update(a);
         update(a);
         update(b);
         update(b);
     }
     }
  public:
  public:
     ITreap() : root(0) {}
     void pushBack(int value) {
    int size() {
         root = merge(root, new Node(value));
         return getC(root);
     }
     }
     void insert(int pos, int v) {
        TN *a, *b;
     void pushFront(int value) {
        split(root, pos, a, b);
         root = merge(new Node(value), root);
         root = merge(a, merge(new TN(v), b));
     }
     }
     int getMax(int l, int r) {
         TN *a, *b, *c;
    void insertAfter(int index, int value) {
         split(root, l, a, b);
        Node *a, *b;
         split(b, r - l + 1, b, c);
        split(root, index, a, b);
         int res = getMaxV(b);
        root = merge(a, merge(new Node(value), b));
    }
     void erase(int index) {
        Node *a, *b, *c;
        split(root, index, a, b);
        split(b, 1, b, c);
        root = merge(a, c);
    }
    void erase(int lIndex, int rIndex) {
         Node *a, *b, *c;
         split(root, lIndex, a, b);
         split(b, rIndex - lIndex + 1, b, c);
        root = merge(a, c);
    }
    int operator[](int index) {
        Node *a, *b, *c;
        split(root, index, a, b);
        split(b, 1, b, c);
         int res = b->value;
         root = merge(a, merge(b, c));
         root = merge(a, merge(b, c));
         return res;
         return res;
    }
    void moveToFront(int lIndex, int rIndex) {
        Node *a, *b, *c;
        split(root, lIndex, a, b);
        split(b, rIndex - lIndex + 1, b, c);
        root = merge(b, merge(a, c));
    }
    void moveToBack(int lIndex, int rIndex) {
        Node *a, *b, *c;
        split(root, lIndex, a, b);
        split(b, rIndex - lIndex + 1, b, c);
        root = merge(a, merge(c, b));
    }
    void reverse(int lIndex, int rIndex) {
        Node *a, *b, *c;
        split(root, lIndex, a, b);
        split(b, rIndex - lIndex + 1, b, c);
        b->rev = 1;
        root = merge(a, merge(b, c));
     }
     }
  };
  };
|}


== Ссылки ==
== Ссылки ==
Теория:
Теория:
* [https://www.youtube.com/watch?v=MLIbII4sBs0&list=PLGhUJWLZ8uQ5Ewplzb1ER29p4-kQme5Yr&index=5 Фолунин В. — Декартово дерево по неявному ключу]
* [http://e-maxx.ru/algo/treap#7 e-maxx.ru &mdash; Неявные декартовы деревья]
* [http://e-maxx.ru/algo/treap#7 e-maxx.ru &mdash; Неявные декартовы деревья]
* [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 &mdash; Декартово дерево по неявному ключу]
* [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 &mdash; Декартово дерево по неявному ключу]
Строка 190: Строка 748:
* [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 &mdash; 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 &mdash; Cartesian tree using implicit keys]
* [http://github.com/ADJA/algos/blob/master/DataStructures/CartesianTreeImplicitKeys.cpp Algos &mdash; Cartesian tree using implicit keys]
Задачи:
Задачи:

Текущая версия от 15:09, 24 мая 2023

TLDR

Multimap с getMinValue

getMinValue(lKey, rKey) 

class Treap {
    inline static minstd_rand gen;

    struct Node {
        int key, priority, value, minValue;
        Node *left = 0, *right = 0;
        Node(int key, int value) : key(key), priority(gen()), value(value), minValue(value) {}
    } *root = 0;

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

    void update(Node *n) {
        if (n)
            n->minValue = min({ getMinValue(n->left), n->value, getMinValue(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);
    }

public:
    void insert(int key, int value) {
        Node *a, *b;
        split(root, key, a, b);
        root = merge(a, merge(new Node(key, value), b));
    }

    void erase(int key) {
        Node *a, *b, *c;
        split(root, key, a, b);
        split(b, key + 1, b, c);
        root = merge(a, c);
    }

    void eraseOne(int key) {
        Node *a, *b, *c;
        split(root, key, a, b);
        split(b, key + 1, b, c);
        if (b)
            b = merge(b->left, b->right);
        root = merge(a, merge(b, c));
    }

    int getMinValue(int lKey, int rKey) {
        Node *a, *b, *c;
        split(root, lKey, a, b);
        split(b, rKey + 1, b, c);
        int res = getMinValue(b);
        root = merge(a, merge(b, c));
        return res;
    }
};

getMinValue(lIndex, rIndex) 

class Treap {
    inline static minstd_rand gen;

    struct Node {
        int key, priority, size = 1, value, minValue;
        Node *left = 0, *right = 0;
        Node(int key, int value) : key(key), priority(gen()), value(value), minValue(value) {}
    } *root = 0;

    int getSize(Node *n) const {
        return n ? n->size : 0;
    }

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

    void update(Node *n) {
        if (n) {
            n->size = getSize(n->left) + 1 + getSize(n->right);
            n->minValue = min({ getMinValue(n->left), n->value, getMinValue(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);
    }

    void splitByIndex(Node *t, int index, Node *&a, Node *&b) {
        if (!t) {
            a = b = 0;
            return;
        }
        int leftSize = getSize(t->left);
        if (leftSize < index) {
            splitByIndex(t->right, index - leftSize - 1, t->right, b);
            a = t;
        } else {
            splitByIndex(t->left, index, a, t->left);
            b = t;            
        }
        update(a);
        update(b);
    }

public:
    void insert(int key, int value) {
        Node *a, *b;
        split(root, key, a, b);
        root = merge(a, merge(new Node(key, value), b));
    }

    void erase(int key) {
        Node *a, *b, *c;
        split(root, key, a, b);
        split(b, key + 1, b, c);
        root = merge(a, c);
    }

    void eraseOne(int key) {
        Node *a, *b, *c;
        split(root, key, a, b);
        split(b, key + 1, b, c);
        if (b)
            b = merge(b->left, b->right);
        root = merge(a, merge(b, c));
    }

    int getMinValue(int lIndex, int rIndex) {
        Node *a, *b, *c;
        splitByIndex(root, lIndex, a, b);
        splitByIndex(b, rIndex - lIndex + 1, b, c);
        int res = getMinValue(b);
        root = merge(a, merge(b, c));
        return res;
    }
};

Multiset с indexOf(key), operator[], lessCount(key), greaterCount(key)

Одинаковые элементы хранятся в нескольких узлах 

class Treap {
    inline static minstd_rand gen;

    struct Node {
        int key, priority, size = 1;
        Node *left = 0, *right = 0;
        Node(int key) : key(key), priority(gen()) {}
    } *root = 0;

    int getSize(Node *n) const {
        return n ? n->size : 0;
    }

    void update(Node *n) {
        if (n)
            n->size = getSize(n->left) + 1 + getSize(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 (key < n->key)
            return indexOf(n->left, key);
        else if (n->key == key)
            return getSize(n->left);
        else
            return getSize(n->left) + 1 + indexOf(n->right, key);
    }

    int getByIndex(Node *n, int index) const {
        int leftSize = getSize(n->left);
        if (leftSize > index)
            return getByIndex(n->left, index);
        else if (leftSize == index)
            return n->key;
        else
            return getByIndex(n->right, index - leftSize - 1);
    }

public:
    int size() const {
        return getSize(root);
    }

    int indexOf(int key) const {
        return indexOf(root, key);
    }

    int operator[](int index) const {
        return getByIndex(root, index);
    }

    void insert(int key) {
        Node *a, *b;
        split(root, key, a, b);
        root = merge(a, merge(new Node(key), b));
    }

    void erase(int key) {
        Node *a, *b, *c;
        split(root, key, a, b);
        split(b, key + 1, b, c);
        root = merge(a, c);
    }

    void eraseOne(int key) {
        Node *a, *b, *c;
        split(root, key, a, b);
        split(b, key + 1, b, c);
        if (b)
            b = merge(b->left, b->right);
        root = merge(a, merge(b, c));
    }

    int lessCount(int key) {
        Node *a, *b;
        split(root, key, a, b);
        int res = getSize(a);
        root = merge(a, b);
        return res;
    }

    int lessEqualCount(int key) {
        Node *a, *b;
        split(root, key + 1, a, b);
        int res = getSize(a);
        root = merge(a, b);
        return res;
    }

    int greaterCount(int key) {
        Node *a, *b;
        split(root, key + 1, a, b);
        int res = getSize(b);
        root = merge(a, b);
        return res;
    }

    int greaterEqualCount(int key) {
        Node *a, *b;
        split(root, key, a, b);
        int res = getSize(b);
        root = merge(a, b);
        return res;
    }
};

Одинаковые элементы хранятся в одном узле 

class Treap {
    inline static minstd_rand gen;

    struct Node {
        int key, priority, nodeSize = 1, subtreeSize = 1;
        Node *left = 0, *right = 0;
        Node(int key) : key(key), priority(gen()) {}
    } *root = 0;

    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 (key < n->key)
            return indexOf(n->left, key);
        else if (n->key == key)
            return getSubtreeSize(n->left);
        else
            return getSubtreeSize(n->left) + n->nodeSize + indexOf(n->right, 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 n->key;
        else
            return getByIndex(n->right, index - leftSize - n->nodeSize);
    }

public:
    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 *a, *b, *c;
        split(root, key, a, b);
        split(b, key + 1, b, c);
        if (b) {
            b->nodeSize++;
            b->subtreeSize++;
        } else {
            b = new Node(key);
        }
        root = merge(a, merge(b, c));
    }

    void erase(int key) {
        Node *a, *b, *c;
        split(root, key, a, b);
        split(b, key + 1, b, c);
        root = merge(a, c);
    }

    void eraseOne(int key) {
        Node *a, *b, *c;
        split(root, key, a, b);
        split(b, key + 1, b, c);
        if (b) {
            b->nodeSize--;
            b->subtreeSize--;
            if (!b->nodeSize)
                b = 0;
        }
        root = merge(a, merge(b, c));
    }

    int lessCount(int key) {
        Node *a, *b;
        split(root, key, a, b);
        int res = getSize(a);
        root = merge(a, b);
        return res;
    }

    int lessEqualCount(int key) {
        Node *a, *b;
        split(root, key + 1, a, b);
        int res = getSize(a);
        root = merge(a, b);
        return res;
    }

    int greaterCount(int key) {
        Node *a, *b;
        split(root, key + 1, a, b);
        int res = getSize(b);
        root = merge(a, b);
        return res;
    }

    int greaterEqualCount(int key) {
        Node *a, *b;
        split(root, key, a, b);
        int res = getSize(b);
        root = merge(a, b);
        return res;
    }
};

Set с find_by_order(index) и order_of_key(key) через __gnu_pbds

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;


Vector

getMinValue(lIndex, rIndex) 

class ImplicitTreap {
    inline static minstd_rand gen;

    struct Node {
        int value, priority, size = 1, minValue;
        Node *left = 0, *right = 0;
        Node(int value) : value(value), priority(gen()), minValue(value) {}
    } *root = 0;

    int getSize(Node *n) {
        return n ? n->size : 0;
    }

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

    void update(Node *n) {
        if (n) {
            n->size = getSize(n->left) + 1 + getSize(n->right);
            n->minValue = min({ getMinValue(n->left), n->value, getMinValue(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 k, Node *&a, Node *&b) {
        if (!t) {
            a = b = 0;
            return;
        }
        if (getSize(t->left) < k) {
            split(t->right, k - getSize(t->left) - 1, t->right, b);
            a = t;
        } else {
            split(t->left, k, a, t->left);
            b = t;
        }
        update(a);
        update(b);
    }

public:
    void pushBack(int value) {
        root = merge(root, new Node(value));
    }

    void pushFront(int value) {
        root = merge(new Node(value), root);
    }

    void insertAfter(int index, int value) {
        Node *a, *b;
        split(root, index, a, b);
        root = merge(a, merge(new Node(value), b));
    }

    void erase(int index) {
        Node *a, *b, *c;
        split(root, index, a, b);
        split(b, 1, b, c);
        root = merge(a, c);
    }

    void erase(int lIndex, int rIndex) {
        Node *a, *b, *c;
        split(root, lIndex, a, b);
        split(b, rIndex - lIndex + 1, b, c);
        root = merge(a, c);
    }

    int operator[](int index) {
        Node *a, *b, *c;
        split(root, index, a, b);
        split(b, 1, b, c);
        int res = b->value;
        root = merge(a, merge(b, c));
        return res;
    }

    void moveToFront(int lIndex, int rIndex) {
        Node *a, *b, *c;
        split(root, lIndex, a, b);
        split(b, rIndex - lIndex + 1, b, c);
        root = merge(b, merge(a, c));
    }

    void moveToBack(int lIndex, int rIndex) {
        Node *a, *b, *c;
        split(root, lIndex, a, b);
        split(b, rIndex - lIndex + 1, b, c);
        root = merge(a, merge(c, b));
    }

    int getMinValue(int lIndex, int rIndex) {
        Node *a, *b, *c;
        split(root, lIndex, a, b);
        split(b, rIndex - lIndex + 1, b, c);
        int res = getMinValue(b);
        root = merge(a, merge(b, c));
        return res;
    }
};

reverse(lIndex, rIndex) 

class ImplicitTreap {
    inline static minstd_rand gen;

    struct Node {
        int value, priority, size = 1, rev = 0;
        Node *left = 0, *right = 0;
        Node(int value) : value(value), priority(gen()) {}
    } *root = 0;

    int getSize(Node *n) {
        return n ? n->size : 0;
    }

    void push(Node *n) {
        if (n && n->rev) {
            swap(n->left, n->right);
            if (n->left)
                n->left->rev ^= 1;
            if (n->right)
                n->right->rev ^= 1;
            n->rev = 0;
        }
    }

    void update(Node *n) {
        if (n)
            n->size = getSize(n->left) + 1 + getSize(n->right);
    }

    Node *merge(Node *a, Node *b) {
        push(a);
        push(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 k, Node *&a, Node *&b) {
        push(t);
        if (!t) {
            a = b = 0;
            return;
        }
        if (getSize(t->left) < k) {
            split(t->right, k - getSize(t->left) - 1, t->right, b);
            a = t;
        } else {
            split(t->left, k, a, t->left);
            b = t;
        }
        update(a);
        update(b);
    }

public:
    void pushBack(int value) {
        root = merge(root, new Node(value));
    }

    void pushFront(int value) {
        root = merge(new Node(value), root);
    }

    void insertAfter(int index, int value) {
        Node *a, *b;
        split(root, index, a, b);
        root = merge(a, merge(new Node(value), b));
    }

    void erase(int index) {
        Node *a, *b, *c;
        split(root, index, a, b);
        split(b, 1, b, c);
        root = merge(a, c);
    }

    void erase(int lIndex, int rIndex) {
        Node *a, *b, *c;
        split(root, lIndex, a, b);
        split(b, rIndex - lIndex + 1, b, c);
        root = merge(a, c);
    }

    int operator[](int index) {
        Node *a, *b, *c;
        split(root, index, a, b);
        split(b, 1, b, c);
        int res = b->value;
        root = merge(a, merge(b, c));
        return res;
    }

    void moveToFront(int lIndex, int rIndex) {
        Node *a, *b, *c;
        split(root, lIndex, a, b);
        split(b, rIndex - lIndex + 1, b, c);
        root = merge(b, merge(a, c));
    }

    void moveToBack(int lIndex, int rIndex) {
        Node *a, *b, *c;
        split(root, lIndex, a, b);
        split(b, rIndex - lIndex + 1, b, c);
        root = merge(a, merge(c, b));
    }

    void reverse(int lIndex, int rIndex) {
        Node *a, *b, *c;
        split(root, lIndex, a, b);
        split(b, rIndex - lIndex + 1, b, c);
        b->rev = 1;
        root = merge(a, merge(b, c));
    }
};

Ссылки

Теория:

Код:

Задачи:

Источник — https://acm.khpnets.info/w39/index.php?title=Расширения_декартова_дерева&oldid=2870