• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie inwersje kontratakują 2

Aruba Cloud - Virtual Private Server VPS
0 głosów
388 wizyt
pytanie zadane 24 grudnia 2022 w C i C++ przez polandonion Dyskutant (7,630 p.)

Witam, zrobiłem zadanie inwersje kontratakują 2 ale mam za mało punktów, bo zrobiłem je iteracyjnie. Wie ktoś może w jaki sposób użyć w nim drzewa przedziałowego? Żadne sensowne wykorzystanie tej struktury w tym problemie nie przychodzi mi do głowy

2 odpowiedzi

+1 głos
odpowiedź 24 grudnia 2022 przez Whistleroosh Maniak (57,400 p.)
wybrane 4 marca 2023 przez polandonion
 
Najlepsza
Skoro inwersja to taka para indeksów (i, j), ze j < i oraz a_j > a_i  to od razu nasuwa się pomysł, żeby iterować się po indeksie i oraz dodawać do wyniku ilość elementów z przedziału [a_i+1, maks] leżących na lewo od indeksu i
+1 głos
odpowiedź 24 grudnia 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 25 grudnia 2022 przez pasjonat_algorytmiki
Napisałem coś takiego: https://github.com/samek567/ZadaniaAlgorytmiczne/blob/main/KoloStaszica/inwersje_kontratakuja.cpp

Wchodzi na 100 w O(n log n). Pomysł jest taki, ze skoro interesują cię tylko elementy większe na lewo, to sortujesz elementy trzymając strukturę wartosc, idx niemalejąco i teraz, wiesz, że wynikiem są elementy przed tobą(po to sortowaliśmy), które mają < idx niz elementy[i].idx. Elementy przed tobą to te nie sprawdzone jeszcze, więc żeby znać ich sumę to robisz drzewo przedziałowe, gdzie przypisujesz im 1 a jak jakis sprawdzisz to zmieniasz na 0. Więc poprostu proste drzewo przedziałowe punkt-przedział z querry i update. Sortowanie ma O(n log n), operacje na drzewach też O(n log n), więc dostajesz O(n log n)

Widzę, że też oglądasz OKI, super przygotowanie do OIJ i OI-a robią.

Podobne pytania

0 głosów
1 odpowiedź 1,606 wizyt
0 głosów
0 odpowiedzi 96 wizyt
pytanie zadane 8 maja 2023 w C i C++ przez Dani Obywatel (1,450 p.)

93,326 zapytań

142,323 odpowiedzi

322,390 komentarzy

62,654 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...