Implementacja seta z idxami / drzewa licznikowego

Question

Wie ktoś może, czy mogę jakoś stosunkowo nietrudno zaimplementować sobie seta z idxami, chodzi mi żebym mógł wykonywać operacje:

- dodaj i usuń element

- znajdź który element ma idx Z

No i żeby ta struktura była posortowana.

Wiem że jest coś takiego jak ordered_set, ale z tym mam kilka problemów:

- żeby tego użyć, trzeba zapamiętać te długie kilka linijek

- problem się robi, jak chce mieć powtórzenia, bo tak trzeba używać jakieś dziwne rzeczy.

- nie wiem jak zrobić tam seta innego niż intow.

Podsumuwując, czy radzicie zapamiętać te linijki do ordered_seta i jakoś nauczyć się jak pisać multiseta, czy może jest jakaś nietrudna do zaimplementowania w czasie zawodow struktura, która umożliwi mi te operacje. Słyszałem o jakiś drzewach BST i kompresji czerwono czarnej, czy jakoś tak, ale jak przeczytałam o tym to trochę mi się odechciało.....

Ciekawi mnie jeszcze jedna rzecz. Czy np można ten problem rozwiązać jakoś stosunkowo łatwo, jak chce mieć złożoność sqrt, zamiast loga.

Z góry dziękuję za pomoc i poświęcony czas!

Answer 1

ordered_set jest chyba najlepszym rozwiązaniem. Działa dla dowolnego typu tak długo jak ten typ ma zdefiniowany operator<. Możesz nawet zrobić template:

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

I wtedy dla structa np. Node robisz:

ordered_set<Node> ordS;

Inną opcją jest zaimplementowanie tego drzewem przedziałowym, ale problem pojawia się gdy wartości są z dużego zakresu np. [0, 1e18]. Wtedy pozostaje albo skorzystanie z kompresji, albo z dynamicznego drzewa przedziałowego, albo ze zbalansowanego BST np. drzewo AVL lub RB (Red-black tree). Tylko takie drzewa BST nie są proste w zaimplementowaniu w trakcie 5-godzinnego konkursu. A ordered_set korzysta już z RB tree (to wynika z rb_tree_tag)

Nie wydaje mi się, ze istnieje prostsze rozwiązanie działające w sqrt(n)