Обработка математики: 100%
images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
03/04/2025 15:32:08

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2758. Декартово дерево с неявным ключом

Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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";});

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);
  }
};

Пример использования:

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";
}

В качестве решения отправлять завершенное определение класса

loading