Dla każdego wymiaru z osobna, i dla każdego odcinka pomiędzy sąsiednimi punktami liczę hash zbioru gatunków które muszą mieć "odwrócone" terytoria wokół torusa żeby dane miejsce było w ich terytorium. Sumuję długości odcinków o identycznych hashach i biorę największą sumę.

Ojej - liczę tak samo. Myślałem, że da się mądrzej niż hashując.
Próbowałem jakoś pamiętać jakie kombinacje prostokątów już wystąpiły i zastanawiałem się czy da się stwierdzić szybko czy dana kombinacja już wystąpiła.
Ostatecznie jednak zrobiłem hashowanie.

Jakby ktoś się zastanawiał to używałem hashowania Zobrista.
Jest to hashowanie popularne np. w szachach.
Każdy prostokąt miał wygenerowaną losowo 64-bitową maskę.
Gdy przechodzimy przez punkt danego prostokąta, xorujemy nasz aktualny hash przez maskę tego prostokąta.
Gdy przejdziemy drugi raz przez punkt tego samego prostokąta - xor wyzeruje ten hash i wróci do odpowiedniej wartości.

Zrobiłem tak samo, ale dodatkowo grupuję hashe po rozmiarze podzbioru - ciekawe, jak bardzo to zmniejsza prawdopodobieństwo kolizji?

Użyłem hasha wielomianowego modulo liczba pierwsza.

Ja miałem bez hashowania. Też robię niezależnie oba wymiary i na koniec wymnażam wyniki. Koncepcyjne chcę zrobić coś takiego: iteruję się po wszystkich jednostkowych odcinkach, ustawiam wszystkie obszary tak, żeby go obejmowały, liczę przecięcie całości i biorę maxa po wszystkich odcinkach. Żeby to zrobić w O(n log n) mam sobie drzewo przedziałowe nad całym odcinkiem, trzymam w nim do ilu obszarów należy dany odcinek jednostkowy oraz maximum na przedziale i liczbę wystąpień maximum. Na początku ustawiam wszystkie przedziały tak, żeby odcinek [0, 1) należał do wszystkich, następnie sortuję wszystkie końce przedziałów, przeglądam je w tej kolejności, jak mijam koniec odcinka, to flipuję go (dodaję -1 na tym co pokrywał i +1 na reszcie) i odczytuję z drzewa przedziałowego aktualną długość przecięcia

Też drzewa przedziałowe.
W jednym wymiarze: niech n_i to bedą węzły, czyli wszystkie końce odcinków, dorzucone brzegi mapy: 0 i max_X.
Jeśli "jesteśmy" w przedziale pomiędzy węzłąmi n_i n_{i+1}, to które odcinki (rzuty prostokąta. jeśli mamy punkty x1<x2, to albo zakazujemy odcinka [x1,x2], albo odcinków [0,x1] i [x2,maxX]) na torusie są wybrane jest jednoznacznie określone. No to sie przespacerujmy po tych przedziałach.
Drzewko przedziałowe: na spodzie ma nasze odcinki pomiędzy węzłami, poziom wyżej poparowana i tak dalej. W każdym węźle trzymamy "liczbę zakazów", wagę - długość niezakazanego obszaru, czyli te obszary, nad którymi nie ciąży zaden zakaz,(oraz dla wygody boki reprezentowanego odcinka pamięci jest dosyć).
Drzewko ma operacje "zakaż" i "pozwól". Wrzucamy w nie odcinek J, ten schodzi po drzewku i jeśli reprezentowany przez węzeł odcinek mieści się w J, to zwiększamy "liczbę zakazów" w węźle (jeśli to metoda 'pozwol', to zmnijeszamy). Jeśli nie, schodzimy do jego dzieci. Wracajac z rekurencji poprawiamy wagę: jeśli liczba zakaz>0, waga =0. Jeśli nie, to waga to waga dzieci.
Waga korzenia to łączna długość odcinków bez zadnego zakazu. Jedna operacja poprawia co najwyzej O(log n) wezlow.

No to teraz juz prosto. Jeśli z pary punktów [x1,x2] wybraliśmy jeden z mozliwych realizacji odcinka na torusie, to zakazujemy albo [x1,x2], albo odcinków [0,x1] i [x2,maxX].
Poczatkowo zakazujemy wszystkich [x1,x2], (zaczynamy jakby sprzed 0),
pętlą po węzłech (przekraczamy dany węzeł i jesteśmy w odcinku na prawo od niego):
... , jeśli przekrodzony węzeł był jednym z punktów [x1 x2], musimy odpowiednio zakazać lub udostepnic odpowiednie odcinki, poprawiamy tak wszystkie. (Ja trzymalem dwie tablice par posortowane raz po pierwszej, raz po drugiej wspolrzednej. Da się bardziej elegancko)
...odczytujemy wagę z korzenia, a nuż jest lepsza niż dotychczasowe rekord.

Ach czyli jednak można było zrobić bez hashowania.

Dzięki!

Krzysztof: Algorytmy randomizowane nie są niemądre!

Szczególnie jeśli potrafisz oszacować prawdopodobieństwo błędu.

W tym przypadku, ponieważ hashowanie Zobrista jest uniwersalną rodziną funkcji hashujących, a liczba par porównywanych hashy <= 2n^2, prawdopodobieństwo błędu <= 2n^2 * 2^(-bits) = 0.5e12 * 2^(-64) <= 3e-8.

Mnie się coś pomyliło i wyszło mi, że to haszowanie ma za duży błąd, a drzew przedziałowych nie wymyśliłem. Mam więc bez haszowania i bez drzew przedziałowych :)

Rozwiązujemy przypadek 1-wymiarowy i zastanawiamy się tak jak w haszowaniu, które odcinki pomiędzy końcami są w jednej grupie (czyli należą do tych samych przecieć i dopełnienień).
Dla uproszczenia dodaję jeden odcinek maksymalny [0, x_max] do zbioru -> to nie wpływa na wynik.
Przeglądam wszystko od lewej do prawej utrzymując 2 stosy:
1. stos początków odcinków -> tu utrzymuję niezmiennik, że na szczycie będzie najdalszy początek odcinka, który nie jest jeszcze zamknięty
2. stos regionów aktywnych, czyli takich, które mogą się jeszcze z czymś scalić - pamiętam je jako para (początek odcinka, wewnątrz którego leży ten region; łączna długość regionu) -> niezmiennik: 1. współrzędna tych par jest ściśle rosnąca.
Mamy wydarzenia:
1. początek odcinka
-> wrzucamy ten początek na pierwszy stos
2. nowy odcinek [a, b]
-> jako początek tego regionu biorę szczyt pierwszego stosu x i dodaje parę (x, b - a) na drugi stos, chyba, że szczycie drugiego stosu jest aktywny region postaci (x, _) -> wtedy dodaję (b - a) do jego drugiej współrzędnej.
3. koniec i-tego odcinka [a, b]:
-> zaznaczam i-ty odcinek jako odwiedzony i zrzucam z pierwszego stosu początki, aż na szczycie będzie początek nieodwiedzonego odcinka
-> z drugiego stosu zrzucam wszystkie regiony (x, l) takie, że x >= a (nasz odcinek [a, b] jest świadkiem na to, że takie regiony nie mogą już się połączyć z dalszymi odcinkami) i aktualizuję wynik: wynik = max(wynik, l).

U mnie też hashowanie, tylko zamiast Zobrista użyłem mnożenia liczb pierwszych modulo P=4294967029.
Wchodzimy do odcinka — mnożymy przez p. Wychodzimy z odcinka — mnożymy przez odwrotność p modulo P.

Ja mam podobnie jak w rozwiązaniach z hashowaniem, ale do identyfikacji zbioru aktywnych przedziałów użyłem pary (ilość_aktywnych_przedziałów, minimalny_prawy_koniec_aktywnego_przedziału). Przy przeglądaniu początków i końców przedziałów w kierunku rosnących współrzędnych (dla różnych zbiorów aktywnych przedziałów) nie powinienem dostać kolizji takich par, więc użyłem ich jako klucze (po zrzutowaniu na long long) w mapie zliczającej wynik dla zbioru przedziałów. Do utrzymywania minimalnego prawego końca aktywnych przedziałów użyłem po prostu priority_queue.

Ja każdemu obszarowi przyporządkowuję ciąg 0-1 tak, że każda liczba odpowiada jednemu prostokątowi, a długość ciągu to liczba prostokątów. Zamiatamy i zamieniamy 0 na 1 i na odwrót gdy przechodzimy przez bok prostokąta. Teraz nad tym ciągiem utrzymuję drzewo hashy i danemu obszarowi przyporządkowuję hash z korzenia.