Potrzebuje struktury która będzie pozwalała na usuwanie elementów oraz opdpowiadała ile elementów jest mniejszych od wartości w złożoności (conajmniej) O(log n)

0

Cześć!
Potrzebuje struktury która będzie pozwalała na usuwanie elementów oraz opdpowiadała ile elementów jest mniejszych od wartości w złożoności (conajmniej) O(log n), wydaje mi się że multiset mogłoby spełniać tą funkcję z pomocą equal_range (lub lower_bound) tylko wtedy dostaję dwa iteratory. Czy jest możliwę stwierdzić ile elementów znajduję się pomiędzy nimi?

np. Mam takiego mulitseta
{1, 2, 2, 3, 3, 3, 4, 4, 4, 4} i chcę wiedzieć ile elementów jest mniejszych niż 4, więc używam magicznej funkcji

int ile_elementow_jest_mniejszych_niz(int liczba)

która zwraca 6

EDIT:
Funkcja musi działać w O(1)

0

std::distance

Dla map nie będzie O(1)

0

map::size działa w O(1) natomiast jeżeli Ty chcesz sobie szukać dla określonej wartości to możesz stworzyć klasę, ktora dziedziczy po multisecie i dodać inkrementowanie konkretnej wartości(np w tablicy jakiejś) podczas insertowania

1

Coś mi się wydaje, że rozwiązujesz jakieś zadanie SPOJ/hackerrank/leetcode/..... i nie możesz przeskoczyć limitu czasowego.
Lepiej będzie jak zapodasz linka do zadania i/lub skopiujesz treść zdania na forum i pokaż swoje rozwiązanie.

0

Nie ma podanych wymaganych złożoności wszystkich operacji, więc może być to pudło, ale co np. z hash table (nie pamiętam już klasek z C++ po ponad 10 latach nieużywania ;) ), gdzie kluczem są te elementy (liczby), a wartością para: krotność (bo multiset) i licznik elementów mniejszych? Tylko przy wstawianiu i usuwaniu trzeba przeiterować po całości i zaktualizować liczniki - coś za coś.

0

no ale jak masz posortowane to znalezienie pozycji nie jest chyba problemem a jak masz pozycję to wiesz ile jest mniej. Z więcej jest trochę gorzej bo trzeba znaleźć pozycję pierwszego większego (jeśli dopuszczasz duble)

1

Potrzebujesz tego: https://codeforces.com/blog/entry/11080

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace std;
using namespace std::__gnu_pbds;

using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    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
}

A gdyby chcieć to ręcznie robić, to byś chciał zrobić samobalansujące się drzewo, które dodatkowo trzyma wielkości swoich prawych i lewych poddrzew, i ostrożnie aktualizować te wartości przy wszystkich wstawianiach i usuwaniach. Można to osiągnąć na drzewach czewono-czarnych, na AVL, pewnie też wielu innych (nie jestem pewien czy da się na takim splayu).

1 użytkowników online, w tym zalogowanych: 0, gości: 1