potwierdzam

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).

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.

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

Dzięki!

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.

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

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.

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.

Ja miałem 2 fft bez liczb Lucasa, wystarczyło pomieszać trochę wzorem F_a * F_b + F_(a - 1) * F_(b - 1) = F_(a + b) i zrobić podobne jak @Maciej, tylko że w drugiej nieparzyste elementy f mnożę przez -1.

Liczby Lucasa wyklikane na Wikipedii :)

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ę.

0. Zamieniam na system binarny, mnożę pisemnie, i zamieniam z powrotem.

@Maciej. Wow. Sam to wymyśliłeś, czy znałeś wcześniej?

2:

Fibonacci multiply(Fibonacci f, Lucas l) {
....auto result = convolve(f, l);
....Lucas reversed(l.size());
....REP(k,l.size()) reversed[l.size()-1-k] = (k%2 ? -1 : 1) * l[k];
....auto r = convolve(f,reversed);
....REP(i,r.size()) {
........int nk = i - (l.size()-1);
........result[abs(nk)] += r[i] * ((nk >= 0 || nk % 2 != 0) ? 1 : -1);
....}
....return result;
}