Всем привет! После достаточно долгого затишья, я решил, что мой вклад растёт слишком медленно пришёл час порадовать вас ещё одной статьёй в блоге :)
2 месяца назад пользователь Perlik выложил статью, в которой описал очень интересную реализованную в STL структуру, которая позволяла очень быстро производить различные операции с подстроками. Некоторое время после этого я тестировал её на различных задачах и, к сожалению, как правило, получал негативный результат — rope оказалась слишком уж медленной, особенно когда речь шла о работе с отдельно взятыми элементами.
На некоторое время я позабыл о той статье. Однако всё чаще я сталкивался с задачами, в которых нужно было реализовать множество, да не простое, а золотое с возможностью узнавать порядковый номер элемента и, напротив, элемент по его порядковому номеру (т.е., порядковую статистику в множестве). Вопрос выполнения этих операций методами стандартной библиотеки достаточно тонкий и актуальный, подтверждением тому можно привести, например, этот и этот блоги. И тут я вспомнил о том, что в комментариях к той статье кто-то упомянул о загадочной структуре данных order statistics tree, которое как раз поддерживает эти две операции и которое как раз реализовано в STL (хотя и только для GNU C++). Тут и началось моё увлекательное знакомство со структурами данных, основанными на политике (policy based data structures), о которых я хочу поведать и вам :)
Итак, приступим. В данной статье я рассмотрю наиболее интересную из реализованных структур — дерево (tree). Нам потребуется подключить следующие библиотеки:
#include <ext/pb_ds/assoc_container.hpp> // Общий файл.
#include <ext/pb_ds/tree_policy.hpp> // Содержит класс tree_order_statistics_node_update
При более внимательном рассмотрении можно обнаружить, что последние два файла содержатся в библиотеке
#include <ext/pb_ds/detail/standard_policies.hpp>
Пространство имён, с которым нам прийдётся работать в современных версиях носит название __gnu_pbds;
Ранее оно называлось pb_ds;
Теперь рассмотрим конкретные структуры.
Шаблон tree
имеет следующий вид:
template<
typename Key, // Тип ключа
typename Mapped, // Тип ассоциированных с ключём данных
typename Cmp_Fn = std::less<Key>, // Функтор сравнения, должен соответствовать оператору <
typename Tag = rb_tree_tag, // Метка, обозначающая тип дерева
template<
typename Const_Node_Iterator,
typename Node_Iterator,
typename Cmp_Fn_,
typename Allocator_>
class Node_Update = null_node_update, // Метка обновления вершин
typename Allocator = std::allocator<char> > // Аллокатор
class tree;
Опытные участники, должно быть, уже заметили, что если инициализировать в шаблоне только первые 2 типа, то мы получим практически точную копию контейнера map
. Сразу оговорюсь, что из этого контейнера можно сделать set
, для этого нужно просто указать вторым аргументом шаблона тип null_type
(в старых версиях null_mapped_type
).
А вот параметры Tag
и Node_Update
в обычном map
'e отсутствуют. Рассмотрим их подробнее.
Tag
— класс, обозначающий структуру дерева, которое мы будем использовать. В STL реализовано три класса, которые мы можем здесь использовать, это rb_tree_tag
, splay_tree_tag
и ov_tree_tag
. На практике, однако, допустимо использование только красно-чёрного дерева, spay_tree и ov_tree же, по всей видимости, используют при обновлении линейную по времени операцию split, что и лишает их возможности к применению при решении олимпиадных задач.
Node_Update
— класс, обозначающий политику обновления инвариантов вершин. По умолчанию он установлен в null_node_update
, т.е., дополнительной информации в вершинах не храниться. Кроме этого, в C++ реализована политика обновления tree_order_statistics_node_update
, которая, собственно, и несёт в себе необходимые операции. Рассмотрим их. Скорее всего, наилучшим способом задания дерева будет следующий:
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
Если мы хотим получить ассоциативный массив, а не множество, в качестве второго аргумента следует использовать тип, соответствующий значению в этом множестве. По всей видимости, дерево поддерживает все те же операции, что и set
(по крайней мере, до этого у меня с ними конфликта не возникало), но кроме этого добавлены две новые функции — это find_by_order()
и order_of_key()
. Первая возвращает итератор на k-ый по величине элемент (отсчёт с нуля), вторая — возвращает количество элементов в множестве, строго меньших, чем наш элемент. Пример использования:
ordered_set X;
X.insert(1);
X.insert(2);
X.insert(4);
X.insert(8);
X.insert(16);
cout<<*X.find_by_order(1)<<endl; // 2
cout<<*X.find_by_order(2)<<endl; // 4
cout<<*X.find_by_order(4)<<endl; // 16
cout<<(end(X)==X.find_by_order(6))<<endl; // true
cout<<X.order_of_key(-5)<<endl; // 0
cout<<X.order_of_key(1)<<endl; // 0
cout<<X.order_of_key(3)<<endl; // 2
cout<<X.order_of_key(4)<<endl; // 2
cout<<X.order_of_key(400)<<endl; // 5
Как мне кажется, наличие такой структуры в STL просто замечательно, т.к. оно позволяет ещё сильнее сузить круг задач, в которых реализация какой-нибудь общеизвестной структуры требует порой больше времени, чем придумывание решения. Напоследок хотелось бы сказать о производительности order_statistics_tree в STL. Для этого я приведу следующую таблицу задач, на которых я её тестировал и результаты по ним.
Решение\Задача | 1028 | 1090 | 1521 | 1439 |
order_statistics_tree, STL | 0.062 | 0.218 | 0.296 | 0.468 |
Дерево Отрезков | 0.031 | 0.078 | 0.171 | 0.078 0.859* |
Дерево Фенвика | 0.031 | 0.062 | 0.062 | |
* В последней задаче для реализации решения за O(mlogn) необходим прямой доступ к вершинам дерева. Без него решение работает за O(mlogn*logn).
Как можно из всего этого видеть, order_statistics_tree сравнительно немного отстаёт от рукописных структур, а порой и вовсе их обгоняет. При этом размер кода сокращается значительно. Отсюда можно сделать вывод, что order_statistics_tree — это хорошо и его можно использовать в контестах.
Кроме tree, я также хотел описать здесь trie — реализованный префиксный бор. Однако, меня смутили некоторые аспекты его реализации, сильно ограничивающие его применимость в олимпиадном программировании, в связи с чем его описание я здесь приводить не буду. Если кому-то интересно, он может самостоятельно попытаться узнать об этой структуре больше.
Полезные ссылки:
— Документация по pb_ds
— Тестирование производительности pb_ds
— Помощь с использованием pb_ds
— Демонстрация использования order_statistics_tree
— Демонстрация использования бора с поиском строк, включающих данную строку в качестве префикса
— Операции с интервалами с помощью самописного класса обновления вершин
— Прочие примеры
Example of trie with search of prefix range.
Problem: 1414
Solution: http://ideone.com/6VFNZl
Is there a way of counting number of strings in the trie with a certain prefix without iterating through them all?
You augment the trie node to also contain a number. Update this number everytime you insert a string into the trie. To get the number of strings which share the prefix, Just traverse the prefix and output the num in the ending node.
Возможно, вам покажутся слегка нетривиальными решения деревом отрезков и деревом Фенвика, особенно, задач 1521 и 1439. Скорее всего, позже я также предоставлю статью, в которой опишу некоторые интересные способы использования этих структур, которые редко встречаются.
======================================================================================= You may be wondered about how I use segment tree and binary indexed tree in my solutions, especially for problems 1521 and 1439. Most likely, later I'll provide an entry about some interesting ways of using this structures, which are quite rare.
Here it is :)
This is really useful. Thanks a lot!
Very useful article! I need order-statistics on a multiset. How should I define the tree as?
As I know, there is no implemented tree multiset in STL. However you can use pair<T,int> as a key where the second element in pair is the time when item has been added.
Apparently, you can. Once I tried to write less_equal instead of less and it started to work as multiset, I even got AC using it in region olympiad)
I can't erase elements with less_equal comparator, e.g. this code output "1"
So I guess it's not very useful thing (or I do something wrong).
UPD: I can delete iterator which I got with lower_bound. But it works incorrectly. This code erase 1, not 0
Wow. then it really sucks. Seems like I only used it with insert operations and strangely enough it worked)
5 years later I can say it is useful in some problems and this helped me today in this problem
glad it helped:)
You can erase elements from the multiset.
Well, actually it works fine and exactly does what you want! The issue is that you're passing
less_equal<int>
as the tree comparator. Therefore it uses the same function forlower_bound()
. By definition of lower_bound function (according to cplusplus.com) it finds the first element not comparedtrue
. Thus returns the first element greater thanval
which is1
in your example.In order to make sure you may even test
set<int,less_equal<int> >
which results the same.What if I want to calculate the index of upper_bound of a particular element? Suppose we have: 1 1 2 3 4 then how to find index(upper_bound(2))?
UPDATE: Maybe it is = order_of_key(number+1) ?
So to erase an element from ordered_set with less_equal I used lower_bound on (element to be erased — 1) and then erased the iterator I got from lower_bound and it works only if the element to be erased is present in the set.
5 years later vol2, lower_bound doesn't work but you can do it like d.erase(d.find_by_order(d.order_of_key(0)) this erases iterator correctly, but it's little slow.
I don't actually know how does it work, but if you use upper_bound instead of lower_bound it woulf work correctly.
Another drawback of using
less_equal
instead ofless
is thatlower_bound
works asupper_bound
and vice-versa. CodeAn excellent deduction.
Thanks this was helpful
in today's leet c?
yes bro
https://leetcode.com/contest/weekly-contest-342/submissions/detail/938214410/
here is my solution.
typedef tree<long long, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
using " less_equal<> " makes it a multiset7 years later, I was using this incorrect template for long time, until recently ended up messing in live contest here.
https://codeforces.com/contest/1998/submission/275629343
where find() method always returning set.end() and so erase was wrong. Even lower_bound was giving some wierd behaviour.
Upd. It seems you have to use lower_bound for upper_bound and vice versa
Now, i could able to erase as
set.erase(set.upper_bound(x));
And passed https://codeforces.com/contest/1998/submission/275639066
What about the comparator i.e. less<int>
typedef tree<int, null_type, less_equal, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
Can we use this in this question? or we can't use it, as I am not able to implement the multiset part
just use the fucking binary search on this problem
The 3rd template argument must be
less_equal<int>
. But adamant, is it the correct way to do this ? Since as far as I know, most of the STL containers require a comparator that offers a strict weak ordering (Not sure of the exact reasons though). So, will there be some drawbacks of trying to construct a multiset this way?To use order-statistics on a multiset: Use:: tree<int, null_type, less_equal, rb_tree_tag, tree_order_statistics_node_update> s;
find_by_order and order_of_key work the same as for a set.
However for searching, lower_bound and upper_bound work oppositely. Also, let's say you want to erase x, use s.erase(s.upper_bound(x)) (as upper bound is considered as lower bound)
This is actually great. Whenever I needed to handle duplicate I used take pair<val,index>. This is much simpler.
.(same comment as above)
А начиная с каких версий плюсов tree<...> компилируется?
Затрудняюсь ответить на этот вопрос :(
Пока только могу сказать, что на некоторых совсем старых версиях необходимо писать null_mapped_type вместо null_type. Например, на 4.3.2, судя по компилятору с http://ideone.com.
what will be the complexity of erase operation? O(logn) or O(n)
O(logn)
Really??
Yes.
Is there any efficient function to merge 2 trees ?
You can do in log(n) if the greatest element of 1 tree is smaller than smallest of other. Otherwise, I don't you have a better option. Tell me as well if you have found something interesting.
How do you merge two non-intersected rbtrees (as in the article) in O(lg n) time? I find that the default join() function takes linear time...
Have you found something interesting about merge ? Im trying to do .join but it throws error.
how can i use it like multiset ?
Main idea is to keep pairs like {elem, id}.
thanks a lot :)
like me.order_of_key({x, 0}) me.find_by_order({x,0}) dose not work.. why??
*me.find_by_order({x,0})
still it does not work.
sure it does work, but you cannot print a pair so you have to do it like this
cout << me.find_by_order(1)->first ;
wtf, find_by_order takes number
how to use find_by_order if I'm using ordered_set with pairs. ~~~~~ typedef tree< pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; ~~~~~
nice technique. worked fine! thanks a lot.
typedef tree<int, null_type, less_equal, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
Hi, adamant, the code files in Useful Links don't seem to work. Could you fix them?
Thanks for this great post. I am looking forward to your next and next next posts.
Can you elaborate please?
For example, the code in "Demonstration of trie with prefix search" cannot run on my computer. I saw that there was some old syntax like the namespace pb_ds. I changed it, then it returned a new error in another place. The truth is I am not good enough to change things any more. I hope that you can update it. (I know that I can use the trie code in one of your comments, but this post would be even better if the cost in Useful Links were also updated)
Thank you.
I can't edit the original files — they're not mine. But here is the correct version: http://ideone.com/BpZlYO
Thank you.
What is the complexity of these function :
find_by_order()
andorder_of_key()
?Logarithmic, I suppose
https://www.e-olymp.com/ru/problems/2961 Is it possible to solve this problem using this algorithm?
[del]
Can anybody share a Java equivalent class for this type of set or a code which acts according to above data structure?
It does not exist.
You may use instead:
I thought of number compression + fenwick tree, but this solution will work for only offline queries. I want to handle online queries. The best I can think of now is Treap + Segment Tree or Treap + Fenwick Tree. But here again is the problem of implementation of mixed data structure, I am unable to think how to implement that. Can you please help me?
у этой штуки правда нету
count
?(понятно, что можно
*s.find_by_order(s.order_of_key(x)) == x
, но не красиво же)Можно s.order_of_key(x + 1) — s.order_of_key(x)
Да, если это инты
Можете ли вы пожалуйста объяснить почему это равносильно функции count ?
Это равносильно bool(count())
спасибо, то есть он лишь проверяет есть ли этот элемент в set-e или нет?
Ну вообще обычно lower_bound с иксом сравнивают
с проверкой на end? тоже не красиво
Any idea on how to use this pre C++11?
How can I use a custom compare function in the "Key comparison functor" section for custom data types?
Just like for regular set..
I can use custom compare function for a set by using operator overloading. I want to know is there any other way to do this for both set and ordered set using lambda expression or just using a compare bool function?
Thank adamant you very much for your nice post.
I suppose you can overload operator and still use
less<T>
. Also you can use functors and lambdas in the way similar as for sets:Why does it only work with lambdas and not functions? On doing
Where
comp
is a comparator function, I get an error.It does not work for me. I tried using custom comparator but getting error. Please resolve my issue. Code Link: https://leetcode.com/submissions/detail/693650301/
I have written cmp struct but when i pass in tree argument it is giving me error.
Sorry, what doesn't work?
works just fine on my side.
P.S. I would really recommend against using
<=
as a comparator, because it's supposed to be anti-reflexive.Is it possible to search for the order of a non-key value by passing a comparator/function ? I sometimes find myself have to use my own tree templates instead because of having to write a search function that can cope with this task.
What is the constant factor of order_statistics_tree though it executes in logarithmic complexity ? I think it's constant factor is very high.
could anyone write the exact thing to use this data structure as map..pls.I'm not able do so.
And what exactly do you want from it? You can use something like that.
as it was mentioned in the article that we can use it as map by defining mapped type .So I tried to do that by couldn't. that's all;)
is this thing a order statistics tree
Can you write the multiset implementation of ordered_set. When I use less_equal then I'm not able to erase from the ordered_set. And when I use the pair for including duplicates I'm not able to use find_by_order({x,0}).
What's wrong with find_by_order({x, 0})?
It gives an error. It says no known conversion. error: no matching function for call to '__gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>::find_by_order()
Wait, find_by_order takes number $$$k$$$ and returns $$$k$$$-th element. What exactly do you expect it to return?..
A number .
I think you should use order_of_key then
Thanks adamant I did that.
Actually find_by_order( x) takes in an integer input because it tells us the element present in the position x. Whereas find_by_order({x, 0}) is a syntax error and it wont work.
can we use it as multiset?
u can use pair<int,int> for manage the duplicate values..
typedef tree<int, null_type, less_equal, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
It is:
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
thank you bro :) it worked for duplicate elements too..
what to do if i want to merge two ordered multisets?
is it legal to use it in ICPC or any region contest ??
How can I erase element from order_set by it's value?
just do
ordered_set<T> st; st.erase(key);
This doesn't work .
ordered_set :: iterator it; it=st.upper_bound(key); st.erase(it); it works;
Thanks bro
You can try this to erase by value from ordered multiset(or wwhatever it's called in technical terms)
How to use Ordered Multiset
To erase by value from Ordered Multiset:
os.erase(os.find_by_order(os.order_of_key(val)));
(Sorry for necroposting) Does anyone know how to compile with the pbds header files on Mac OS X ? I think the g++ command is configured to use clang by default, and so it is not directly available. I've tried adding ext/pb_ds into the include folder (the same way you would enable bits/stdc++.h) but instead new dependencies come up.
For me, I installed the latest version of gcc (gcc 9.3.0_1) and compiled with gcc-9. It works on Mojave and Catalina and it should work on High Sierra (but I haven't tested it).
To install gcc-9, I used brew and the command
brew install gcc@9
(Again, sorry for necroposting) There is an important step that I've so-far seen all the mac g++ setup instructions ignore/skip. I also installed gcc through brew, but neither bits/stdc++.h header nor pbds data structures seemed to work. Putting the bits/stdc++.h file manually in the /usr/local/include folder allowed me to at least solve the header problem, but trying the same method for pbds spawned a lot of dependency issues.
The problem was that brew sets up the g++ command as g++-10 so that it doesn't clash with the default g++ command mac provides. So, alias-ing g++ to g++-10 in the .bashrc/.zshrc file would be enough for solving the issue if you compile using the terminal. But if you compile using an editor and the editor directly uses the /usr/bin/g++ binary for compilation, then alias-ing g++ wouldn't work anymore. For example, most of the popular VSCode extensions for CP I've seen use /usr/bin/g++ to compile. I wasn't aware that this was the root of the issue and had been missing pbds structures for a long time. The way to solve it is to simlink g++ to g++-10 and prepend it to the PATH variable so that the simlink is prioritized before the default g++.
(Replace the version names with your g++ versions)
cd /usr/local/Cellar/gcc/10.2.0_4/bin
ln -s ./c++-10 ./c++
ln -s ./g++-10 ./g++
Finally, put in your .bashrc/.zshrc file:
export PATH=/usr/local/Cellar/gcc/10.2.0_4/bin:$PATH
I might even find it useful myself if I ever need to setup a mac again in future.
(Sorry for Necroposting). But I have to update the details as from M1 onwards (possibly Big Sur) configurations have been changed. The
Cellar
directory is not available at/usr/local
anymore. You can do the following instead.cd /opt/homebrew/Cellar/gcc/12.2.0/bin
ln -s ./c++-12 ./c++
ln -s ./g++-12 ./g++
export PATH=“/opt/homebrew/Cellar/gcc/12.2.0/bin:$PATH”
Did you manage to solve PBDS issue on your mac ? Doing all above doesn't solve the PBDS issue.
Thanks for the updates.
Yes, PBDS seems to work for me. I'm running macOS Ventura on M1 (Btw I had to reinstall the command-line tools when updating from Big Sur to Ventura). Can you elaborate on the exact issue you're facing, or possibly provide some error logs?
Also, did you try compiling a source code that uses PBDS from the terminal? Because I've fixed similar issues for others who were compiling/running from an editor/IDE, but the main culprit was actually the editor. The editor might fail if you didn't properly point it toward the Homebrew g++.
I am also using ventura 13.2 on M1. I tried both on sublime build and manually on terminal to run a sample code. It shows the following error.
The
.zshrc
profile looks like as mentioned in the above command. I tried to add the missing file, then got reported for another missing file and so on. In fact theext/pb_ds
directory I put there myself.I think it might have to do with the configs in
.zshrc
. I checked my.zshrc
file and there seem to be some additional env variables I defined but I forgot why. I have these at the very top of the.zshrc
file:Check if you have similar paths and modify them accordingly before putting them in
.zshrc
. Also, the last path there (/Users/drswad/Desktop/CP/Setup/include
) is just for any custom header files. I put my debugging template andtestlib.h
in there, so that they always get included in every program on my PC and the editor linter doesn't complain with red squiggly lines.Also, try reinstalling command-line tools with
xcode-select --install
.Let me know if they resolve your issue.
Note on using
less_equal
as comparison function to use it as a multiset:_GLIBCXX_DEBUG
must not be defined, otherwise some internal check will fail.find
will always returnend
.lower_bound
works likeupper_bound
in normal set (to return the first element > it)upper_bound
works likelower_bound
in normal set (to return the first element >= it)find_by_order
andorder_of_key
works properly (unlike the 2 functions above).Some code to verify the points above: Try it online!
adamant, while discussion, someone suggested that the time complexity of using it as a set is amortized log(n), and this post says that it means that in some cases that can be O(n). I wonder if that is true ?? If yes, is there an alternative to policy based data structures ?? Here is one solution
It shouldn't be. And even if so, what's the deal? It will always be O(n log n +q log n) if you use set of numbers of size n and run q queries.
but this link line 4 says :
and if that's the case, won't the complexity be q*n instead of qlog(n) ?? which I suspect might be the reason of my solution getting TLE using policy based data structure while the editorial using treap and getting accepted (having same time complexity ).
Please guide me through it as I use this data structure very frequently.
It can't be. By definition amortized complexity means that algorithm is guaranteed to have such executing time if it's divided By the numbers of queries. When they say "few" they mean it
So, I should treat it as the worst time complexity of this data structure ?
If you don't revert operations and don't need it persistent then basically yes. In your case it is likely to be too large constant factor. But I'll look into it later.
Can i merge two ordered_set ? if it can be what will be its complexity?
Как реализовать ordered set для произвольных самописных структур, если для структуры прописан оператор < ?
UPD: Уже ответил на свой вопрос.
Thanks,it just got me an AC.
If someone is having trouble to use these in windows with mingw compiler, try to find hash_standard_resize_policy_imp.hpp0000644 in MinGW\lib\gcc\mingw32\6.3.0\include\c++\ext\pb_ds\detail\resize_policy and rename it to hash_standard_resize_policy_imp.hpp. I dont know why it is named like this.
thanks bro ...do you know why it name like this ... why wrong extension is given to it..
I have defined a
bool cmp(pair<int,int> a, pair<int, int> b)
for comparing pairs. Is it possible to use that as the comparator for theordered_set
?Thank you this really helped me.
Is this actually STL? I only see files with gcc's implementation of the c++ standard library. Actual STL is quite old (the linked post references SGI's docs, and SGI doesn't even exist any more)
Nope, this has nothing to do with the C++ standard library.
This is a GNU extension, so it has nothing to do with the STL which (incorrectly) refers to the C++ standard library.
STL doesn't even refer to the C++ standard library. STL is the Standard Template Library from long ago which heavily influenced the C++ standard library but is not the same thing. https://stackoverflow.com/a/5205571
I know, but here and in many other places "STL" is incorrectly used to refer to the C++ standard library.
The first returns an iterator to the k-th largest element (counting from zero)
Shouldn't it be
the k-th smallest element
? adamantHow to merge two ordered sets?
Iterate through every element in the smaller set and append it to the bigger one
thanks brother
A very Useful article helped me in a lot of places. Thank you for your contribution.
When to use BIT over PBDS .. if they perform same thing instead of memory constrain
When to use BIT over PBDS other then memory limit
https://codeforces.com/contest/459/problem/D can we solve this question using pbds ? Its giving me runtime error — https://codeforces.com/contest/459/submission/81689503
can we use pair in place of int ??
Sure, why not. We may use any type with operator < defined.
Is
insert
not too slow? I tried 10^7 insertions and it took over a minute.Doesn't find_by_order(k) returns the kth smallest element in the set? In the article the values given seems like the kth smallest ones not the largest ones
Shouldn't this line
be
because X.find_by_order(1) clearly returns 2nd smallest number.
Just saw this post and I am wondering can https://codeforces.com/contest/237/submission/2804338 be the first submission using pbds? (I did not actually used pbds in this submission just included it as part of my template.) IIRC, Gerald used to see my usage of this trick in Dec, 2013 and asked about its usage.
Can I make the ordered set get the first element greater than x or even greater than or equal?
*find_by_order(order_of_key(x)) -- this will be first greater or equal element than x if u wanna only greater *find_by_order(order_of_key(x+1)) <-- write this
Tree Order Statistics / C++ STL: Policy based Template
This comment about not using find is only when we're using indexed multimap and multiset? What if we want to check if the tree contains a given value? How can we do that if the find doesn't work?
Edit: Nvm, i've found a way, posting here if its useful for anyone:
Please note
erase(key)
does not work if you are usingordered_map
typedef tree< int, map_value_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_map;
Thanks a lot bro
What do we need to do to erase the specific element from the ordered_set ?
Just do
s.erase(5)
, considering the name of your ordered_set iss
and the element that you intend to remove is5
.can we use this in IOI
How to remove an element from an ordered_set ?
Regarding the trie implementation, is there an easy way to iterate over it? I'd like to be able to give a word one letter at a time, and get back the node I'm currently on, without redoing any work.
Could not implement it in time for today's E :(
I also used this for the E today, but I found this blog was too confusing so I used this tutorial instead: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/ lmao.