Zadanie Zdjęcia OIG. Zamiatanie oraz sqrt decomposition/drzewa przedział - przedział

pytanie zadane 16 lutego 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,560 p.)
otagowane ponownie 17 lutego 2023 przez pasjonat_algorytmiki

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/G9Fs1g7hoS5uG9eeV84d0Axr/site/?key=statement

Gdzieś wyczytałem, że można to zrobić jakimś drzewem przedziałowym, ale mam problem, bo nie wiem jak napisać drzewo przedziałowe 2D. Umiem zwykłe drzewa przedziałowe 1D, ale 2D, to sobie trochę nie wyobrażam jak to zrobić. Ma ktoś pomysł?

A i umiem zrobić to zadanie na przedziale 1D,w sensie mam os liczbową, i drzewo przedział punkt, z dodaniem na przedziale i odczytem w punkcie, bo x_i oraz y_i są w przedziale [-200000,200000], więc starczy mi pamięci.

Z góry dziękuję za pomoc i poświęcony czas!

1 odpowiedź

odpowiedź 17 lutego 2023 przez Whistleroosh Maniak (57,400 p.)
wybrane 17 lutego 2023 przez pasjonat_algorytmiki

Najlepsza

Drzewo przedziałowe 2D to trochę overkill. Z tego co wiem na OI nie mają prawa pojawić się przepływy, więc tym bardziej nie będzie takich skomplikowanych struktury danych jak drzewo przedziałowe 2D, sufiksowe itd.

Ale jak chcesz się z nimi zapoznać to zapytanie na drzewie o d wymiarach działa w O(log^dn). Tutaj opis jak działają

Samo zadanie można zrobić prościej. Słowa kluczowe: zamiatanie + drzewo przedziałowe 1D

komentarz 17 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,560 p.)

A myślałem żeby jakoś w takiej kolejności to przetwarzać(od lewej do prawej) i skakać x-ami po wszystkich jakie są końce prostokątów, bo wydaje mi się, że warto zdjęcie wbić, tam gdzie jest chociaż jedno obramowanie(dowolny bok), tylko nie wiem jak odpowiadać na zapytania:

Ma to sens?

1	komentarz 17 lutego 2023 przez Whistleroosh Maniak (57,400 p.) Tak i to jest właśnie zamiatanie. Potrzebne będzie drzewo przedział-przedział

komentarz 17 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,560 p.)

Dodaj wartośc na przedziale i odczytaj maxa?

1	komentarz 17 lutego 2023 przez Whistleroosh Maniak (57,400 p.) Tak, dokładnie

komentarz 17 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,560 p.)

Oooo, nie wiem czy to co wymyśliłem to zamiatanie, ale drzewo przedzial - przedział robię na tym pionowym(tym co przesuwam) i wrzucam na vector, początki i końce zdjęcia(po x) i jak jest początek zdjęcia to będę dodawał jeden na przedziale y1do y2(początku), a jak koniec, to będę odejmować jeden na przedziale y1, y2.

No to część 2d już jest ogarnięta, tylko dalej nie wiem, jak obsłużyć te 2 operacje na zwykłym drzewie przedziałowym 1D. (dodaj na przedziale i odczytaj maxa). Jeśli będę wstanie robić te operacje w logu to wejdzie.

Chwila chwila, A tak sobie myślę o jednej rzeczy. Skoro n<=10^5,to nie mogę zamiast tego skomplikowanego drzewa, zrobić to pierwiastkami? Dzielę sobie te drzewo przedzialowe 1D na odcinki po pierwiastek i wjedzie O(N*sqrt(N) + O(N lg N))?,te drugie O(N lg N), bo muszę to początki i końce posortować. Bo dodanie działa łatwo poprostu idę po całym przedziale o długości sqrt(resztki, max 2 razy(dopełnienie z lewej i prawej strony)), a większość sobie będę skakał co sqrt , a zapytanie to będę sobie skakał.

1	komentarz 17 lutego 2023 przez Whistleroosh Maniak (57,400 p.) Możesz spróbować pierwiastkiem, powinno być na styk czasowo

1	komentarz 17 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,560 p.) Zacząłem implementować sqrt, ale na poczatku chciałem sprawdzić, ile pkt i dostanę za samo zamiatanie i trzymanie statycznie na vectorze ile jest O(N*400000), i wchodzi nawet na 40pkt, więc sqrt, może wejdzie, zobaczymy.

komentarz 17 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,560 p.)

Kurcze, piłuję już piątą godzinę, te sqrt(2 testy nie przechodzą czasu, i daje 90pkt), przyśpieszyłem na counting sorta, ale co ciekawe, jakbym zamiast funkcji odczytaj_max(tam tracę baaardzo dużo czasu) robiłbym, to szybciej, to przeszło z połową zapasu. Myślałem, żeby zamiast tej funkcji, zrobić drzewo przedizałowe punkt-przedział wyników, ale to też nie przeszło. Wiem że da się to jakoś przyśpieszyć(pewnie jakaś kolejka monotonniczna / set, raczej set, bo kolejka monotonniczna to chyba jednak nie). Napewno da się to jakoś dopiłować, bo funkcja dodaj, się wyrabia w czasie. Masz może pomysł?

Kod:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Przedzial
{
    int x;
    int poczatek_y;
    int koniec_y;
    int ile_dodajemy; // Ile dodajemy(poczatek zdjecia, +1) czy odejmujemy(koniec zdjecia, -1)
    bool operator < (const Przedzial &przedzial) const
    {
        if (x == przedzial.x)
            return ile_dodajemy > przedzial.ile_dodajemy;
        return x < przedzial.x;
    }
};

int n = 0, k = 447, ile_przedzialow = 402000 / k, x_1 = 0, x_2 = 0, y_1 = 0, y_2 = 0, max_wyn = 0; // K ~ sqrt(max(N))
vector<Przedzial> przedzialy_wejscie;
vector<Przedzial> przedzialy;
vector<int> stat; // Ile wbite aktualnie w miejscu;
vector<int> ile_dodajemy_przedzial;
vector<int> max_przedzial;
vector<int> counting_sort_poczatki[400001];
vector<int> counting_sort_konce[400001];

inline void counting_sort()
{
    for (int i = 0; i <= 4e5; ++i)
    {
        for (int j = 0; j < counting_sort_poczatki[i].size(); ++j)
            przedzialy.push_back(przedzialy_wejscie[counting_sort_poczatki[i][j]]);
        for (int j = 0; j < counting_sort_konce[i].size(); ++j)
            przedzialy.push_back(przedzialy_wejscie[counting_sort_konce[i][j]]);
    }
}

inline void dodaj(int a, int b, int val)
{
    a += 2e5, b += 2e5;
    int w_jakim_przedziale_a = a / k, w_jakim_przedziale_b = b / k;

    // Dodajemy w innych przedzialach niz A i B
    for (int i = w_jakim_przedziale_a+1; i < w_jakim_przedziale_b; ++i)
        ile_dodajemy_przedzial[i] += val;

    // Dorownujemy na przedziale A
    for (int i = a; i <= min(w_jakim_przedziale_a * k + k-1,b); ++i)
        stat[i] += val;

    // Dorownujemy w przedziale B
    if (w_jakim_przedziale_a != w_jakim_przedziale_b)
        for (int i = b; i >= w_jakim_przedziale_b * k; --i)
            stat[i] += val;

    // Sprawdzamy max-a w przedziale A
    max_przedzial[w_jakim_przedziale_a] = -1000000;
    for (int i = w_jakim_przedziale_a * k; i < w_jakim_przedziale_a * k + k; ++i)
        max_przedzial[w_jakim_przedziale_a] = max(max_przedzial[w_jakim_przedziale_a], stat[i]);

    // Sprawdzamy max-a w przedziale B
    max_przedzial[w_jakim_przedziale_b] = -1000000;
    for (int i = w_jakim_przedziale_b * k; i < w_jakim_przedziale_b * k + k; ++i)
        max_przedzial[w_jakim_przedziale_b] = max(max_przedzial[w_jakim_przedziale_b], stat[i]);
}

inline int odczytaj_max()
{
    int wyn = 0;
    for (int i = 0; i < ile_przedzialow; ++i)
        wyn = max(wyn,max_przedzial[i] + ile_dodajemy_przedzial[i]);
    return wyn;
}

int main()
{
    // O(N*sqrt(N) + N) - zamiatanie (zamiast drzewa przedzial-przedzial(dodaj na przedziale, i odczytaj maxa) mamy pierwiastek). N, bo trzeba posortowac zdjecia(mozna counting sortem)
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> x_1 >> y_1 >> x_2 >> y_2;
        counting_sort_poczatki[x_1+200000].push_back(przedzialy_wejscie.size());
        przedzialy_wejscie.push_back({x_1,y_1,y_2,1});

        counting_sort_konce[x_2+200000].push_back(przedzialy_wejscie.size());
        przedzialy_wejscie.push_back({x_2,y_1,y_2,-1});
    }

    counting_sort();

    stat.assign(402000,0);
    ile_dodajemy_przedzial.assign(ile_przedzialow,0);
    max_przedzial.assign(ile_przedzialow,0);

    for (int i = 0; i < 2*n; ++i)
    {
        dodaj(przedzialy[i].poczatek_y,przedzialy[i].koniec_y,przedzialy[i].ile_dodajemy);
        max_wyn = max(max_wyn,odczytaj_max());
    }

    cout << max_wyn << '\n';

    return 0;
}

komentarz 17 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,560 p.)

Ufff, przeszło na 100. Dodałem linię 105:

if (przedzialy[i].ile_dodajemy == 1)
            max_wyn = max(max_wyn,odczytaj_max());

Bo jeśli jest zamykający, to nie potrzebuję liczyc max wyniku, bo on nigdy nie polepszy, funkcja odczytaj_max(), więc zamiast 2N razy wywołam ją N razy.

Takie to piłowanie sqrt, żeby przeszło musiałem wprowadzić chyba z 4 opytymalizacje. Opisze krótko kod, jakby się ktoś kiedyś męczył:

NA POCZĄTEK DWIE BARDZO WAŻNE RZECZY: jak implementujesz sqrt decomposition do daj sobie jakąś mała stałą k, np k = 3, lub k = 4 lub k = 5, żeby było Ci łatwiej na kartce sobie rozważac casy. A potem robisz poprostu w 1 lini zamiast k = 3, zmieniasz na k = 447 lub inna i masz, bo tak to ciężko Ci wyłapać błędy jak odrazu dasz K = 447, lub takie duże.

Druga to taka, że jak napiszesz dla k = 3, to pozmieniaj sobie tą stałą (dla testu czy dobrze działa), tylko w jednej linii, tam gdzie deklarujesz k = 3, zmien na k = 2, k = 1, k = 5, k = 4, k = 22, k = 24, k = 26.... I tak sobie potestuj. I odpalaj dla każdego K program i sprawdzaj, czy się wywali. Jak Ci się wywali, to szybko to odkryjesz.

(co ciekawe w teście przykładowym nie przechodzi jednego(czas), ale właściwe wszystkie.) O(N*sqrt(N) + N), N*sqrt(N), bo do jest to sqrt decomposition, N, bo to jest counting sort. Co ciekawe, jak niedawno uczyłem się tego sqrt decomposition, to myślałem, że to kompletne bzdury(skoro umiem pisać drzewo punkt-przedział oraz przedział-punkt), ale okazało się, że baardzo się przydaje, zamiast przedział - przedział(które jest trudniejsze). A samo sqrt decomposition ma 10lini w tym kodzie, i jest przejrzyste.

Jedna rzecz apropo stałej K. sqrt(200000) = 447.2135955, więc ja dałem K = 447, może być trochę więcej / trochę mniej. Jako optymalizację, chciałem podejśc do tego chytrze (oszukać matematykę, ale się nie udało :) pomyślałem sobie, tak skoro opóźnia funkcja odczytaj_max, do zwiększę k, np do 800, bo tam będę robił mniej skoków, będzie to kosztem, tego że więcej operacji, będę robił w małym przedziale, ale myślałem ,że to da radę. Ale jednak matma jest matmą, punkty zaczęły mi schodzić z 90 do 80,70 jak coraz bardziej zwiększałem stałą). Praktycznie zawsze stała K = sqrt(N) jest optymalna. Chyba że się robi baaardzo dużo skoków, a mało aktualizacji w małych przedziałach.

Program jest dośc jasny, tak jak pisaliśmy wyżej. Idziemy zmiotką (patrz rysunek kilka komentarzy wyżej), i sprawdzamy max_wyn. Jak się zaczyna jakieś zdjęcie, to dodajemy na przedziale y1 do y2 1, a jak się kończy jakieś zdjęcie, to odejmujemy 1, na przedziale y1 do y2.

Końcowy kod dający 100, z sqrt decomposition:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Przedzial
{
    int x;
    int poczatek_y;
    int koniec_y;
    int ile_dodajemy; // Ile dodajemy(poczatek zdjecia, +1) czy odejmujemy(koniec zdjecia, -1)
    bool operator < (const Przedzial &przedzial) const
    {
        if (x == przedzial.x)
            return ile_dodajemy > przedzial.ile_dodajemy;
        return x < przedzial.x;
    }
};

int n = 0, k = 447, ile_przedzialow = 402000 / k, x_1 = 0, x_2 = 0, y_1 = 0, y_2 = 0, max_wyn = 0; // K ~ sqrt(max(N))
vector<Przedzial> przedzialy_wejscie;
vector<Przedzial> przedzialy;
vector<int> stat; // Ile wbite aktualnie w miejscu;
vector<int> ile_dodajemy_przedzial;
vector<int> max_przedzial;
vector<int> counting_sort_poczatki[400001];
vector<int> counting_sort_konce[400001];

inline void counting_sort()
{
    for (int i = 0; i <= 4e5; ++i)
    {
        for (int j = 0; j < counting_sort_poczatki[i].size(); ++j)
            przedzialy.push_back(przedzialy_wejscie[counting_sort_poczatki[i][j]]);
        for (int j = 0; j < counting_sort_konce[i].size(); ++j)
            przedzialy.push_back(przedzialy_wejscie[counting_sort_konce[i][j]]);
    }
}

inline void dodaj(int a, int b, int val)
{
    a += 2e5, b += 2e5;
    int w_jakim_przedziale_a = a / k, w_jakim_przedziale_b = b / k;

    // Dodajemy w innych przedzialach niz A i B
    for (int i = w_jakim_przedziale_a+1; i < w_jakim_przedziale_b; dodaje++i)
        ile_dodajemy_przedzial[i] += val;

    // Dorownujemy na przedziale A
    for (int i = a; i <= min(w_jakim_przedziale_a * k + k-1,b); ++i)
        stat[i] += val;

    // Dorownujemy w przedziale B
    if (w_jakim_przedziale_a != w_jakim_przedziale_b)
        for (int i = b; i >= w_jakim_przedziale_b * k; --i)
            stat[i] += val;

    // Sprawdzamy max-a w przedziale A
    max_przedzial[w_jakim_przedziale_a] = -1000000;
    for (int i = w_jakim_przedziale_a * k; i < w_jakim_przedziale_a * k + k; ++i)
        max_przedzial[w_jakim_przedziale_a] = max(max_przedzial[w_jakim_przedziale_a], stat[i]);

    // Sprawdzamy max-a w przedziale B
    max_przedzial[w_jakim_przedziale_b] = -1000000;
    for (int i = w_jakim_przedziale_b * k; i < w_jakim_przedziale_b * k + k; ++i)
        max_przedzial[w_jakim_przedziale_b] = max(max_przedzial[w_jakim_przedziale_b], stat[i]);
}

inline int odczytaj_max()
{
    int wyn = 0;
    for (int i = 0; i < ile_przedzialow; ++i)
        wyn = max(wyn,max_przedzial[i] + ile_dodajemy_przedzial[i]);
    return wyn;
}

int main()
{
    // O(N*sqrt(N) + N) - zamiatanie (zamiast drzewa przedzial-przedzial(dodaj na przedziale, i odczytaj maxa) mamy pierwiastek). N, bo trzeba posortowac zdjecia(mozna counting sortem)
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> x_1 >> y_1 >> x_2 >> y_2;
        counting_sort_poczatki[x_1+200000].push_back(przedzialy_wejscie.size());
        przedzialy_wejscie.push_back({x_1,y_1,y_2,1});

        counting_sort_konce[x_2+200000].push_back(przedzialy_wejscie.size());
        przedzialy_wejscie.push_back({x_2,y_1,y_2,-1});
    }

    counting_sort();

    stat.assign(402000,0);
    ile_dodajemy_przedzial.assign(ile_przedzialow,0);
    max_przedzial.assign(ile_przedzialow,0);

    for (int i = 0; i < 2*n; ++i)
    {
        dodaj(przedzialy[i].poczatek_y,przedzialy[i].koniec_y,przedzialy[i].ile_dodajemy);
        if (przedzialy[i].ile_dodajemy == 1)
            max_wyn = max(max_wyn,odczytaj_max());
    }

    cout << max_wyn << '\n';

    return 0;
}

Mam kilka pytań.

1 - Znasz jakiś fajne źródło do nauki drzewa (przedział - przedział)? Tego nie umiem zaimplementować. Umiem tylko punkt-przedział i przedział-punkt.

2 - Znasz jakieś fajne zadania na drzewa przedział - przedział

3 -Znasz jakieś fajne zadania na zamiatanie?, ja natknąłem się tylko na kopalnia złota z OI-a, zrobię je (wydaje się być fajne)

4 - Są jeszcze jakieś techniki na takich przedziałach 2d, typu zamiatanie?

5 - Jak działają sumy prefiksowe 2D?, czy to też jest takie trudne, jak drzewa przedziałowe 2D?

5 - Co to drzewo Fenwicka?, wyczytałem, że podobno przyśpiesza drzewo przedziałowe, gdy masz zapytania offline. Ale nwm czy dobrze to zrozumiałem / wyczytałem o co w nich chodzi.

ZAMIATANIE JEST SUPER!!!!

Dzięki poraz kolejny za pomoc! (sorki, że tyle pytań, mam nadzieję, że to nie problem)

komentarz 17 lutego 2023 przez Whistleroosh Maniak (57,400 p.)

Zawsze mi mówiono, że ten trick z pierwiastkiem to nie jest coś na co można wpaść samemu, to trzeba po prostu znać. To rzadko kiedy się przydaję, ale warto umieć, bo np. Gang Biciaków (czyli to najtrudniejsze zadanie z I etapu) dało się rozwiązać tym trickiem. Co do pytań, zrobię sobie małą reklamę :) Tutaj jest moja implementacja drzew przedziałowych. Pisałem je juz po tym jak skończyłem zabawę z competitive programming, więc nie gwarantuje że nie ma tam żadnych bugów. A co do teorii to najlepszym źródłem jak zawsze jest CP-algorithms.

Zadanka za chwilę jakies poszukam.

Jeśli chodzi o przedziały 2D to nie kojarzę innych technik, ale możesz spojrzeć na geometrię i jak liczyć np. parę najblizszych punktów, otoczkę wypukłą itp.

Sumy prefiksowe 2D są zdefiniowane tak: s[i][j] to suma wszystkich wartosci w prostokącie o lewym górnym wierzchołku w (0, 0) i prawym dolnym w (i ,j). Zadanie: jak policzyć tablicę s?

Drzewo Fenwicka to takie szybsze drzewo przedziałowe. Działa w pamięci liniowej (czyli mniej niż zwykle d. przedziałowe), zapytania działają w O(logn) ale przeważnie będą trochę szybsze od zwykłej implementacji d. przedziałowego bo stała będzie mniejsza. W Przygodach Bajtazara jest chyba opis jak je zaimplementować

1	komentarz 17 lutego 2023 przez Whistleroosh Maniak (57,400 p.) edycja 18 lutego 2023 przez Whistleroosh Zadania na drzewo przedział-przedział: Oceny Koleje Marchew (ze staszica) Nawiasy kwadratowe kontratakują (ze staszica) tetris 2D (znowu staszic) Te ze staszica są trochę prostsze

1	komentarz 17 lutego 2023 przez Whistleroosh Maniak (57,400 p.) edycja 18 lutego 2023 przez Whistleroosh Jedyne zadanie na zamiatanie które pamiętam to Zamek

komentarz 17 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,560 p.)

@Whistleroosh,

Dzięki za tak obszerne komentarze! Widzę, że fajne rzeczy masz na githubie, więc napewno się przyjrzę! Jeszcze raz dzięki za zadanka.

A co do sum prefiksowych to włączenia i wyłączenia. S[i][j] = A[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1].

Dochodzę do siebie, bo tym zamiataniu xD, ta technika jest super. Pamiętam jak jakiś rok temu patrzyłem na to zadanie, i myślałem że to jakiś kosmos dla geniuszy oświeconych xD

komentarz 17 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,560 p.)

@Whistleroosh,

A propos sqrt, to wydaje mi się, że często nawet jak n<=10^6, to często wchodzi na np. 70pkt, a jak N <= 5*10^5, to też często wchodzi, nie mówiąc już jak N <= 10^5 lub N <= 2*10^5. Czy nawet trochę więcej.

komentarz 18 lutego 2023 przez Whistleroosh Maniak (57,400 p.)

Jeszcze wracając do tego pierwiastka to warto żebyś nauczył się o tym algorytmie Mo. On też działa w O(nsqrt(n)), ale wyobraźmy sobie taki problem, że mamy tablicę n liczb i q zapytań. Każde zapytanie pyta ile jest różnych liczb w tablicy na pozycjach a...b Tą metodą z której skorzystaliśmy w tym zadaniu nie da się tego szybko zrobić, ale algorytm Mo jak najbardziej zrobi to w chyba O((n+q)sqrt(n))