tgoop.com/sbornik_olprog/233
Create:
Last Update:
Last Update:
ordered_set в C++
Что делать, если обычного set из C++ недостаточно, так как хочется:
Но при этом лень писать Фенвика, ДО или ДД
А вот ordered_set умеет:
- s.find_by_order(k)
- выдает итератор на k-ый по отсортированному порядку элемент
- s.order_of_key(x)
- выдает количество чисел меньших x
Рассмотрим его использование на примере:
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> // Обязательная строка 1, что б использовать ordered_set
#include <ext/pb_ds/tree_policy.hpp> // Обязательная строка 2, что б использовать ordered_set
using namespace __gnu_pbds; // Обязательная строка 3, что б использовать ordered_set
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // Обязательная строка 4, что б использовать ordered_set
int main()
{
ordered_set<int> s; // Создаем ordered_set
s.insert(5);
s.insert(10);
s.insert(1);
s.insert(7);
// Можно считать, что элементы в s сейчас в таком порядке: 1, 5, 7, 10
cout << s.order_of_key(6) << "\n"; // Выдаст 2, так как числа 1 и 5 меньше, чем 6
cout << *s.find_by_order(2) << "\n"; // Выдаст 7, так как это число второе (индексация с 0) по порядку
return 0;
}
НО! Эта штука медленнее, чем тоже самописное декартово дерево, поэтому если умеете его писать, то лучше использовать его
Теория + задачи:
📚 Пост на кф - еще чуть теории + код + замер таймингов на задачах с Тимуса
📚 Пост на кф 2 - как сделать сумму элементов на отрезке. Сам так не делал, но попробовать можно
💻 Задача с Тимуса 1 - можно решать и другими структурами, но потренить пойдет
💻 Задача с Тимуса 2 - уже посложнее, надо что-то еще придумать
Контест и ответы на частые вопросы в посте автора
Теги: #алгоритмы #std #контест #set
Автор: https://www.tgoop.com/KogutIvanTutoring