Pomysł na algorytm który szybko sprawdzi czy kwadraty nachodzą na siebie w układzie kartezjańskim

Mam takie zadanie:
Mały Bajtek na swoje siódme urodziny dostał od rodziców aparat fotograficzny. Od tego czasu uwielbia robić zdjęcia każdej nowo poznanej osobie. Każde zdjęcie, które zrobi, wywiesza na tablicy korkowej w swoim pokoju. Od urodzin minęło parę miesięcy i tablica jest już mocno zapełniona. Niektóre zdjęcia są całkowicie zasłonięte, inne częściowo... Jeszcze inne, najnowsze, są widoczne w całości.

Kiedy Bajtek przyczepia nowe zdjęcia pinezkami, zastanawia się, ile spośród dotychczas wywieszonych zdjęć przebija każda z nowych pinezek. Chłopiec jest ciekaw, ile zdjęć może maksymalnie przebić jedna taka pinezka. Pomóż Bajtkowi zaspokoić ciekawość.
Zadanie

Napisz program, który

wczyta ze standardowego wejścia opis zdjęć znajdujących się na tablicy korkowej Bajtka,
wyznaczy maksymalną liczbę zdjęć, które może przebić pinezka wbita w tablicę,
wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita () - jest to liczba zdjęć na tablicy. W każdym z następnych wierszy znajdują się po cztery liczby całkowite. W wierszu -szym zapisane są liczby , , , ( oraz i ), poddzielane pojedynczymi odstępami. Są to współrzędne zdjęcia w układzie kartezjańskim na tablicy: to współrzędne lewego dolnego, natomiast to współrzędne prawego górnego rogu zdjęcia. Przyjmujemy, że pinezka wbita w punkt przebije to zdjęcie, jeśli oraz .
Wyjście

Twój program powinien wypisać w pierwszym i jedynym wierszu wyjścia jedną liczbę całkowitą - maksymalną liczbę zdjęć, które może przebić pinezka wbita w pewnym miejscu tablicy.
Przykład

Dla danych wejściowych:

5
-1 -1 1 2
0 -2 3 0
2 2 3 3
-1 -1 1 2
2 -1 4 1

poprawną odpowiedzią jest:

3

Wydaje mi się że trzeba jakoś użyć drzewa i kolejkę priorytetową, mógłby mi ktoś pomóc to rozwiązać?
LINK DO TREŚCI ZADANIA
LINK DO TESTOWANIA

Zgubiłeś formuły texowe.
Zamiatanie + drzewo przedziałowe wydaje się wzorcówką.

to może jednak trochę rozwinę podpowiedź bo to jednak nie są wcale łatwe tematy do wygooglania jak się robi to po raz pierwszy.
Zamiatanie jest bardzo proste i polega na posortowaniu po jednej współrzędnej i dalej przetwarzaniu elementów w tej kolejności. Jak element się zaczyna to dodajemy go do miotły (tą współrzędną po której nie sortowalismy), jak element się kończy to zdejmujemy go z miotły. Napisanie odpowiedniej miotły jest zwykle najtrudniejszym wyzwaniem, bo potrzebujemy struktury do której będziemy dodawać i odejmować, a także odpytywać zwykle w czasie co najwyżej logarytmicznym. Więcej tutaj: https://en.wikipedia.org/wiki/Sweep_line_algorithm.

W tym wypadku na miotłę nada się wspominane drzewo przedziałowe, a dokładnie rzecz biorąc drzewo licznikowe, opisane tutaj:
https://main2.edu.pl/main2/courses/show/17/39/

i jeszcze dla potomności bardzo dobry wykład Jakuba Radoszewskiego o którym wspominał Afish o drzewach przedziałowych który trochę przepadł w otchłani internetu, ale udało mi się go odkopać tutaj:
https://docs.google.com/document/d/e/2PACX-1vTUqM_TS74FHo_p1FWfE1doBs9IFzo6bea2QlzJeyeTditv2LmltZzJ0eZzlwwW-yleMyd6oyHEORiX/pub

Edit: Tak, bez drzewa segmentowego nie przejdzie, 3 ostatnie testy mają timeout. Z drzewami segementowymi i zamiataniem przechodzi ze sporym zapasem czasu.

czy nie dałoby się tego zrobić na drzewie czwórkowym (quadtree)?

Bardzo Dziękuje za pomoc, mam nawet pomysł na to zadanie i niestety problem :P, zbiorę współrzędne zdjęć i posortuje je według pierwszej współrzędnej x, stworzę jednowymiarowe drzewo przedziałowe, teraz (załóżmy że D to dolna współrzędna zdjęcia na osi y a G to górna) chciałbym dodawać 1 w przedziale [D, G] każdego zdjęcia którego pierwszy x jest mniejszy niż drugi x tego pierwszego zdjęcia, a następnie odjąć 1 w przedziale [D,G] i sprawdzać max przebicia, aż w ten sposób przejdę przez cały wektor, ale jak dodać 1 do całego przedziału [D, G] a nie dodawać wartości do drzewa przedziałowego? Musiałbym zrobić drzewo dwuwymiarowe? Czy coś takiego ma sens ?

Suchy702 napisał(a):

Bardzo Dziękuje za pomoc, mam nawet pomysł na to zadanie i niestety problem :P, zbiorę współrzędne zdjęć i posortuje je według pierwszej współrzędnej x, stworzę jednowymiarowe drzewo przedziałowe, teraz (załóżmy że D to dolna współrzędna zdjęcia na osi y a G to górna) chciałbym dodawać 1 w przedziale [D, G] każdego zdjęcia którego pierwszy x jest mniejszy niż drugi x tego pierwszego zdjęcia,

OK moża i tak. Osobiście skłaniam się do uproszczenia zamiatania poprzez reprezentację obu współrzędnych x. Tzn dla każdego prostokąta r = (x1, y1, x2, y2), dodać do struktury reprezentującej oś X oba końce przedziału wraz z dodatkowymi informacjami, t.j (x1, start, r) i (x2, koniec, r). I takie dane posortować po współrzędnej x, a następnie po rodzaju (początek, koniec). Zauważ, że wtedy problem jest dosyć podobny do nawiasowania - wiesz ile jest otwartych przedziałów, kiedy przedział się zamyka, a nawet do którego prostokąta należy przedział - co moim zdaniem upraszcza zamiatanie.

a następnie odjąć 1 w przedziale [D,G] i sprawdzać max przebicia, aż w ten sposób przejdę przez cały wektor, ale jak dodać 1 do całego przedziału [D, G] a nie dodawać wartości do drzewa przedziałowego?

Tu zaczynasz kombinować. Powinno to wyglądać ta:

• napotkałeś początek odcinka na osi x -> cyk +1 w przedziale [D, G] do drzewa przedziałowego.
• napotkałeś koniec odcinka na osi x -> cyk -1 w przedziale [D, G] w owym drzewie.
• Czy aby na pewno musisz sprawdzać przebicia przechodząc przez wszystkie y? Zastanów się, czy jesteś w stanie wzbogacić drzewo przedziałowe o jakieś pożyteczne informacje.

ale jak dodać 1 do całego przedziału [D, G] a nie dodawać wartości do drzewa przedziałowego? Musiałbym zrobić drzewo dwuwymiarowe? Czy coś takiego ma sens ?

Nie ma takiej potrzeby. Może źle interpretujesz zastosowanie drzewa przedziałowego dla tego zadania? W tym wypadku jeżeli dla przedziału [y1,y2] w drzewie przedziałowym jest wartość 5, tzn że 5 odcinków pokrywa cały przedział [y1, y2]. Odcinki te niekoniecznie muszą pokrywać tylko przedział [y1, y2], mogą być znacznie większe.

Dodając nowy przedział niekoniecznie dodajesz nowy wierzchołek w drzewie. Przede wszystkim zmieniasz przetrzymywaną wartość w niektórych wierzchołkach. To czy wymaga to dodania nowego wierzchołka to inna kwestia i zależy od tego czy drzewo konstruujesz statycznie czy leniwie/dynamicznie. Zauważ też, że wierzchołki w drzewie zawsze reprezentują przedział, którego długość odpowiada potędze dwójki.

Pomoglibyście mi zaimplementować to drzewo tak aby dodawać na przedziałach ? Bo nie radzę sobie z tym

Moja implementacja dynamicznie rozwijanego drzewa wygląda następująco:

#include <memory>
using namespace std;

struct Segment {
    int start;
    int end;

    bool intersects(const Segment &other) const {
        return  other.start < end && start < other.end;
    }
    bool covers(const Segment &other) const {
        return start <= other.start && other.end <= end;
    }
};

class SegmentTree {
    unique_ptr<SegmentTree> left_;
    unique_ptr<SegmentTree> right_;
    int load_ = 0;
    Segment segment_;

public:
    SegmentTree(int start, int end) {
        segment_ = Segment{ start, end };
    }

    void remove(const Segment &change_segment, int val) {
        add(change_segment, -val);
    }

    void add(const Segment &change_segment, int val) {
        if (segment_.intersects(change_segment)) {
            if (change_segment.covers(segment_)) {
                load_ += val;
            } else {
                expand();
                if (left_->segment_.intersects(change_segment))
                    left_->add(change_segment, val);
                if (right_->segment_.intersects(change_segment))
                    right_->add(change_segment, val);
            }
        }
    }

private:
    void expand() {
        if ((segment_.end - segment_.start) > 1 && !left_ && !right_) {
            auto mid =  segment_.start + (segment_.end - segment_.start) / 2;
            left_ = make_unique<SegmentTree>(segment_.start, mid);
            right_ = make_unique<SegmentTree>(mid, segment_.end);
        }
    }
};

Ważne uwagi:

• Drzewo zawiera przedziały zamknięte z jednej strony i otwarte z drugiej. To znaczy, że każdy wierzchołek reprezentuje segment/przedział [start, end). Konwencja typowa dla kolekcji w cpp.
• To drzewo nadal należy wzbogacić o dodatkowe statystyki pozycyjne, aby dało rozwiązać się zadanie maksymalnego przebicia. Specjalnie usunąłem ten fragment.
• unique_ptr, jeżeli się z tym nie spotkałeś, jest opakowaniem na wskaźnik, dzięki czemu nie musisz operować na gołych wskaźnikach. Destruktor unique_ptr zadba o de-alokację przetrzymywanych danych dynamicznych, co skraca kod i generalnie jest dobrą praktyką.
• Drzewo przedziałowe zawsze będzie miało 0 lub dwa poddrzewa. Nie ma takiej możliwości/potrzeby by istniało tylko 1 poddrzewo, ponieważ rozmiary przedziałów są kolejnymi potęgami 2, a więc rozmiary zawsze (aż do liścia) da się je podzielić przez 2.
• Dodawanie wywołuje się rekurencyjnie dla lewego i prawego poddrzewa o ile przedziały, które reprezentują, przecinają się z dodawanym przedziałem.
• Dodawanie przestanie wywoływać się rekurencyjnie, gdy zejdzie do wierzchołka, który całkowicie pokrywa.

Jeszcze dla porównania dodam implementację tablicową, iteracyjną od dołu drzewa.
Ponownie bez query dla maksimum.
Tak jak powiedział @Afish jest szybsza, sprawdzarka twierdzi, że dwa razy.
Zwracam także uwagę, że implementacji od dołu modyfikuje więcej wierzchołków (prawego i lewego sąsiada) w stosunku do rekurencyjnej, która dałem wcześniej.

inline int next_power_of_2(int num) {
    num--;
    num |= num >> 1;
    num |= num >> 2;
    num |= num >> 4;
    num |= num >> 8;
    num |= num >> 16;
    num++;
    return num;
}

class SegmentTree {
    // 0 index is unused
    vector<int> load_;
    vector<int> max_load_;
    int start_;
    int end_;
    size_t leafs_base_;
    static constexpr size_t root_index_ = 1;

public:
    SegmentTree(int start, int end) {
        auto num_leafs = next_power_of_2(end - start);
        leafs_base_ = num_leafs;
        load_.resize(2 * num_leafs, 0);
        max_load_.resize(2 * num_leafs, 0);
        start_ = start;
        end_ = end;
    }

    int max_load() const {
        // ciach ... tu byl kod dla maksimum :)
    }

    void remove(int segment_start, int segment_end, int val) {
        add(segment_start, segment_end, -val);
    }

    void add(int segment_start, int segment_end, int val) {
        auto l = leafs_base_ + segment_start - start_;
        auto r = l + (segment_end - segment_start - 1);

        load_[l] += val;
        // ... ;)
        if (l != r) {
            load_[r] += val;
            // ... ;)
        }

        while (l >= root_index_) {
            if (l < r - 1) {
                if (is_left_child(l)) {
                    load_[right_sibling(l)] += val;
                    // ciach ... tu byl kod dla maksimum :)
                }
                if (is_right_child(r)) {
                    load_[left_sibling(r)] += val;
                    // ciach ... tu byl kod dla maksimum :)
                }
            }

            // ciach ... tu byl kod dla maksimum :)

            l = parrent(l);
            r = parrent(r);
        }
    }

private:
    inline size_t left_child(size_t pos) { return 2 * pos; }
    inline size_t right_child(size_t pos) { return 2 * pos + 1; }
    inline bool is_left_child(size_t pos) { return pos % 2 == 0; }
    inline bool is_right_child(size_t pos) { return pos % 2 == 1; }
    inline size_t right_sibling(size_t pos) { return pos + 1; }
    inline size_t left_sibling(size_t pos) { return pos - 1; }
    inline size_t parrent(size_t pos) { return pos / 2; }
};

Dzięki Wielkie @nalik za pomoc i poświęcenie mi tyle czasu w końcu coś z tego zrozumiałem, zrobiłem statyczne drzewo złożone z segmentów które mają wartość przyb (przybite do danego przedziału) i max_pod (ile pod tym przedzialem jest przybite), algorytm oddawania szuka rekurencyjnie odpowiedniego przedziału, zmienia wartość przyb i idzie w górę drzewa zmieniając wartości max_pod (dzięki temu przyb korzenia + max_pod korzenia to aktualny wynik) moja funkcja dodaj jest chyba podobna do twojej z pierwszego drzewa @nalik kod:

#include <bits/stdc++.h>

using namespace std;

const int ABS = 200000;
const int DRZEWO_MAX_SIZE = 400001;

int do_kolejnej_potegi_2(int n){
    int dwa = 2;
    while (dwa < n)
        dwa *= 2;
    return dwa;
}

class Zdjecie{
public:
    int x;
    int poczatek;
    int koniec;
    bool przypnij;

    Zdjecie(int x, int poczatek, int koniec, bool przypnij){
        this->x = x;
        this->poczatek = poczatek;
        this->koniec = koniec;
        this->przypnij = przypnij;
    }

    bool operator <(Zdjecie const & zdj){
        if (this->x != zdj.x)
            return this->x < zdj.x;
        else{
            if (this->przypnij == true){                       //jesli x maja taka sama wartosc najpierw bierzemy tego ktory
                return true;                                   //powinien byc przypiety
            }
            else{
                return false;
            }
        }
    }
};

class Segment{
public:
    int poc;
    int kon;
    int przyp = 0;
    int max_pod = 0;
};

class SegmentTree{
public:
    vector<Segment> tab;
    int wynik = 0;

    void wstaw_liscie(int rozmiar){
        for (int lisc = 0; lisc < rozmiar; lisc++){
            tab[rozmiar + lisc].poc = lisc;
            tab[rozmiar + lisc].kon = lisc;
        }
    }

    void wstaw_przedzialy(int rozmiar){
        for (int glebokosc = rozmiar / 2; glebokosc > 0; glebokosc /= 2){
            for (int przedzial = glebokosc; przedzial < glebokosc * 2; przedzial++){
                tab[przedzial].poc = tab[przedzial * 2].poc;
                tab[przedzial].kon = tab[przedzial * 2 + 1].kon;
            }
        }
    }

    SegmentTree(){
        int rozmiar = do_kolejnej_potegi_2(DRZEWO_MAX_SIZE);
        tab.resize(rozmiar * 2 + 1);
        wstaw_liscie(rozmiar);
        wstaw_przedzialy(rozmiar);
    }

    void uaktualnij_max(int indeks){
        indeks /= 2;
        while (indeks > 0){
            tab[indeks].max_pod = max(tab[indeks * 2].przyp + tab[indeks * 2].max_pod,
                                      tab[indeks * 2 + 1].przyp + tab[indeks * 2 + 1].max_pod);
            indeks /= 2;
        }
    }

    void dodaj(int indeks, int poczatek, int koniec, int val){
        if (tab[indeks].poc >= poczatek && koniec >= tab[indeks].kon){
            tab[indeks].przyp += val;
            uaktualnij_max(indeks);
        }
        else{
            if (tab[indeks * 2].kon >= poczatek)
                dodaj(indeks * 2, poczatek, koniec, val);
            if (tab[indeks * 2 + 1].poc <= koniec)
                dodaj(indeks * 2 + 1, poczatek, koniec, val);
        }
    }

    void przypnij(int poczatek, int koniec){
        dodaj(1, poczatek, koniec, 1);
    }

    void odepnij(int poczatek, int koniec){
        dodaj(1, poczatek, koniec, -1);
    }

    void przypnij_lub_odepnij(Zdjecie zdj){
        if (zdj.przypnij)
            przypnij(zdj.poczatek, zdj.koniec);
        else
            odepnij(zdj.poczatek, zdj.koniec);
        wynik = max(wynik, tab[1].max_pod + tab[1].przyp);
    }

    void pokaz_wynik(){
        cout << wynik;
    }
};

int main() {
    int n, L, D, P, G;
    cin >> n;
    SegmentTree drzewo;
    vector<Zdjecie> zdjecia;
    for (int i = 0; i < n; i++){
        cin >> L >> D >> P >> G;
        L += ABS;
        D += ABS;
        P += ABS;
        G += ABS;
        zdjecia.push_back(Zdjecie(L, D, G, true));
        zdjecia.push_back(Zdjecie(P, D, G, false));
    }
    sort(zdjecia.begin(), zdjecia.end());
    for (Zdjecie zdj : zdjecia){
        drzewo.przypnij_lub_odepnij(zdj);
    }

    drzewo.pokaz_wynik();
  return 0;
}

kod przechodzi wszystkie testy :D

Super, gratuluję. Jak będziesz miał jeszcze czas to przestudiuj opracowanie, oraz inne opracowania, które udostępnili w ramach tego projektu.