Warning: mkdir(): No space left on device in /var/www/tgoop/post.php on line 37

Warning: file_put_contents(aCache/aDaily/post/sbornik_olprog/--): Failed to open stream: No such file or directory in /var/www/tgoop/post.php on line 50
Сборник Олпрогера@sbornik_olprog P.233
SBORNIK_OLPROG Telegram 233
ordered_set в C++

Что делать, если обычного set из C++ недостаточно, так как хочется:
1️⃣Узнавать сколько чисел меньше x
2️⃣Находить k-ое по порядку число?

Но при этом лень писать Фенвика, ДО или ДД 😔

А вот 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
Please open Telegram to view this post
VIEW IN TELEGRAM
👍22👎1



tgoop.com/sbornik_olprog/233
Create:
Last Update:

ordered_set в C++

Что делать, если обычного set из C++ недостаточно, так как хочется:
1️⃣Узнавать сколько чисел меньше x
2️⃣Находить k-ое по порядку число?

Но при этом лень писать Фенвика, ДО или ДД 😔

А вот 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

BY Сборник Олпрогера




Share with your friend now:
tgoop.com/sbornik_olprog/233

View MORE
Open in Telegram


Telegram News

Date: |

But a Telegram statement also said: "Any requests related to political censorship or limiting human rights such as the rights to free speech or assembly are not and will not be considered." You can invite up to 200 people from your contacts to join your channel as the next step. Select the users you want to add and click “Invite.” You can skip this step altogether. The visual aspect of channels is very critical. In fact, design is the first thing that a potential subscriber pays attention to, even though unconsciously. With Bitcoin down 30% in the past week, some crypto traders have taken to Telegram to “voice” their feelings. Polls
from us


Telegram Сборник Олпрогера
FROM American