Moje rozwiązanie wygląda jakoś tak:

Dla każdej osoby będziemy w każdym momencie wiedzieć, czy ma '0', '1', czy też nic nie wiemy '?'. Zaczynamy od stanu, w którym na każdej pozycji znajduje się '?'.

Gdy krawędź prowadzi ze '?' do '?', to ponieważ każdy stan, w którym na pozycji a był '0', a na pozycji b był '1', będzie miał odpowiadający stan, w którym na pozycji a będzie '1', a na pozycji b również '1'. Oba stany będą miały tę samą liczebność, więc po przejściu tą krawędzią każdy stan, w którym a i b mają różne wartości, będzie miał parzystą liczbę możliwości.

Możemy więc założyć, że wartości na pozycjach a i b są równe. Schodzimy rekurencyjnie do stanu, w którym oba są '1' lub oba są '0'.

Jeśli krawędź prowadzi z '1' do '?', '? do '0', lub '1' do '0', to po prostu zamieniamy te wartości miejscami.

Ponieważ zejście w dół zmniejsza liczbę '?' o 2, to złożoność takiej rekurencji będzie O(2^(n/2)*m).

Moje rozwiązanie dostało 7 punktów, ale nie wiem jaką to ma złożoność.

Dla każdej spójnej składowej trzymam drzewo decyzyjne, które odpowiada na pytania: dla danej konfiguracji, ile jest początkowych konfiguracji, które do niej prowadzą, modulo 2. Drzewo zawiera pytania o pozycje w jakiejś kolejności (gotowy lub nie).

Gdy spójne się łączą, to łączę drzewa: w liściach jednego drzewa wstawiam wskaźniki do drugiego drzewa.

Gdy mamy rozkaz (a, b), to przekształcam drzewo tak, żeby pierwsze pytania były o pozycje a, b. I teraz liczę xora dwóch poddrzew (a tak, b nie) xor (a nie, b tak) i wstawiam to jako poddrzewo (a nie, b tak).

Cachuję wszystko, żeby nie liczyć dwa razy tego samego:
* nigdy nie tworzę dwóch identycznych poddrzew (cachuję pary dzieci i szukam przy tworzeniu nowego poddrzewa)
* wysuwanie pytania o daną pozycję do korzenia poddrzewa
* łączenie poddrzew
* xorowanie poddrzew

Tak

Czy to jest rozwiązanie dla pełnego zadania? Mam problem z obsługą zapytania o dodanie/usunięcie krawędzi w tym miejscu

Cześć

Tak mnie zastanawia, jak patrzycie na AI, a być może w przyszłości SI (Swarm Inteligence)? Czujecie się zagrożeni, że to, czego się tyle czasu uczyliście i ćwiczyliście może stać się niepotrzebne, bo samo AI to ogarnie? Czy może zakładacie, że to zatrzyma się na wspomaganiu pracy umysłowej, bez wpływu na liczbę miejsc pracy? Czy może jeszcze inaczej - dotychczasowe stanowiska pracy umysłowej znikną, ale pojawią się inne, których jeszcze nie dostrzegamy?
Wielka szansa umożliwiająca skok technologiczny w każdym aspekcie nauki, czy niebezpieczeństwo, nad którym możemy za jakiś czas przestać panować?

"Może ktoś ma prostsze podejście?" - stary, masz rozwiązanie "z książki" (powiedzenie na modłę pierwszego akapitu https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK) i jeszcze się pytasz czy może ktoś ma prościej xD. Szacun

Mam do siebie żal, że nie skojarzyłem, że dynamiczną spójność offline się robi w O(n log n). Sam opisywałem parę lat temu na potyczkowym forum istotnie bardziej skomplikowaną wersję tego dla wyższych spójności https://sio2.mimuw.edu.pl/c/pa-2020-1/forum/137/1885/ w zadaniu Trzy Drogi :<. Aczkolwiek w tym zadaniu tutaj nie umiałem nawet w O(n log n) rozwiązać podproblemu "graf się nie zmienia, a wszystkie zapytania są na końcu" xd

Brawo Krzysiek! Bardzo fajne rozwiązanie.

Alternatywnie można odwrócić czas i zrobić link-cuta, który ma następujące operacje:
- dodaj krawędź
- usuń krawędź
- zaznacz wierzchołek - wykonane przy napotkaniu zapytania
- znajdź najbliższy zaznaczony wierzchołek i odznacz wierzchołek - wykonywane w pętli przy napotkaniu przemalowania, póki zaznaczone wierzchołki znajdują się w przemalowywanej kuli

Moje rozwiązanie jest offline i działa w O((n+q) log (n+q)). Może ktoś ma prostsze podejście?

Zbudujmy sobie drzewo przedziałowe nad ciągiem modyfikacji lasu, które pozwala odpowiadać na zapytania postaci "czy wierzchołek v został pomalowany przez jakąś operację w przedziale [l;r]". Gdy mamy taką strukturę, to na zapytania możemy łatwo odpowiadać binsearchując moment przemalowania wierzchołka.

W każdym węźle drzewa trzymamy skompresowany las: zostawiamy wszystkie wierzchołki, których dotyczą operacje w przedziale, a resztę maksymalnie kontraktujemy. Zapisujemy sobie mapowanie wierzchołków pomiędzy tymi grafami. Każdy wierzchołek ojca przechodzi w dziecku na:
- wierzchołek jeśli występuje tam
- krawędź - pamiętamy wtedy też odległość w oryginalnym grafie do końców tej krawędzi
Dla każdego wierzchołka trzymamy jeszcze wartość max(promień - dystans) po kulach, które go zawierają. To wystarcza by odpowiadać na zapytania, i można robić binsearch na drzewku by mieć pojedynczy log.

Czy dobrze rozumiem zadanie?

5
-3 0 4 -2 3

Daje 29?

Potwierdzam

https://easyupload.io/iml4yc

https://easyupload.io/wd3b44

1) testy 1 do 100: 5 <= n,m <= 10
2) testy 101 do 200: 10 <= n,m <= 100
3) testy 201 do 300: 100000 <= n <= 200000, 300000 <= m <= 400000

Potwierdzam

Potwierdzam

Mój algorytm zliczania jest trochę inny, ale też O(n log n).

Idę prawym końcem po A. Dla każdego x trzymam strukturę danych, która zawiera zbiór punktów, w których trzeba porozdzielać A, i zlicza liczbę możliwości. Gdy przesuwam się w prawo po A, to te punkty, które są w aktualnym przedziale monotonicznym będą przesuwać się w prawo, a wcześniejsze stoją w miejscu.

Każdą strukturkę trzeba zmieniać tylko wtedy, gdy dzieje się coś ważnego:
* dodanie nowego punktu; trzeba to zrobić dla każdego x takiego, że x-1 | c-2; tych dzielników jest średnio log c
* koniec przedziału monotonicznego; to jest istotne tylko dla tych x, które są krótsze od długości przedziału

Żeby nie trzeba było poprawiać każdej struktury cały czas, to trik jest taki, że po każdej operacji struktura liczy sobie "jaki byłby końcowy wynik, gdyby od teraz już nie trzeba było nic poprawiać". Jak jest jakaś zmiana, to odejmujemy ten przewidywany wynik, robimy operację, i dodajemy nowe przewidywanie.

Żeby dało się to liczyć szybko, potrzebuję dla obu typów punktów rozdzielających dwóch liczb: suma pozycja(i) oraz suma i * pozycja(i).