Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Определить класс "Декартово дерево с неявным ключом"
Операции
создать пустой набор // ``ITreap<int> t;``
количество элементов // ``int kol=t.size();``
получить/изменить i-й // ``auto v=t[i]; t[i]=4;``, где 0<=i<t.size()
удалить `i`-й // ``t.erase(i);``
вставить значение `v` перед i-м // ``it.insert(i,v);``
внутренний итератор // t.foreach([&](int& v){ cout<<v<<"\n";});
```c++
template <typename T>
class ITreap {
struct node {
int x,y; T v;
node *left=nullptr, *right=nullptr;
node(T v) : x(1), y(rand()),v(v) { }
void update() { x=1+(left?left->x:0)+(right?right->x:0); }
};
node *root=nullptr;
pair<node*, node*> split(node* t, int k) { ... } // разделить на 2 дерева из k и size()-k вершин
node* merge(node* t1, node* t2) {...} // слить 2 дерева
void free(node *t) {
if(!t) return;
free(t->left);
free(t->right);
delete t;
}
node* find(int k) {...} // найти узел с номером k
void foreach(std::function<void (T&)> f, node *p) { ... }
public:
ITreap(){}
~ITreap() { free(root); }
int size() const { return root?root->x:0; }
T& operator[](int k) { ... }
T operator[](int k) const { ... }
void insert(int k, T v) { ... }
void erase(int k) { ... }
void foreach(std::function<void (T&)> f) {
foreach(f,root);
}
};
```
Пример использования:
```c++
int main()
{ ITreap<int> t;
t.insert(0,10); // {10}
t.insert(1,20); // {10,20}
t.insert(1,15); // {10,15,20}
t.foreach([&](int& v){ cout<<v<<"\n";});
t[2]=25; // {10,15,25}
t.erase(1); // {10,25}
cout<<t[0]<<"\n";
cout<<t[1]<<"\n";
}
```
В качестве решения отправлять завершенное определение класса
Начало
Рабочее место участника
Учебные задачи: АиСД. Деревья. Множества, отображения, хеш-таблицы