Jak użyć sum prefiksowych?

Siemka,

podpowie ktoś tylko jak użyć w tym zadaniu sum prefiksowych? Dostałem je dawno temu ale do tej pory nie wiem jak je rozwiązać (używając sum prefiksowych). Byłbym wdzięczny za nakierowanie / podpowiedź. Z góry za komentarze.

Zadanie: link
Mój kod bez użycia sum prefiksowych (za wolny, daje mi około 50%):

#include <bits/stdc++.h>
 
using namespace std;
 
bool dest[1001][1001];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int n, m, q;
    cin >> n >> m >> q;
 
    int powi = n * m, zni = 0;
 
    while (q --) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a ++, b ++;
 
        for (int i = a; i <= c; i ++) {
            for (int j = b; j <= d; j ++) {
                if (!dest[i][j]) {
                    zni ++;
                    dest[i][j] = 1;
                }
            }
        }
    }
 
    cout << powi - zni;
}

Czemu uważasz, że to zadanie jest na sumy prefiksowe?

@polandonion: Przepraszam za trywialną uwagę, a nie można zsumować obszarów zniszczeń i odjąć od rozmiaru tego czegoś?

nie można zsumować obszarów zniszczeń i odjąć od rozmiaru tego czegoś?

Nie, gdyż mogą się nakładać i wtedy wyjdzie źle.

Po pierwsze przerób kod, tak by w main było mało:

#incldue <vector>
#incldue <iostream>

struct Range {
   int from, to;
};

struct Rect {
   Range x;
   Range y;
};

std::istream& operator>>(std::istream& in, Rect& a)
{
    return in >> x.from >> y.from >> x.to >> y.to;
}

class City
{
public:
    explicit City(int n, int m) : n{n}, m{m}
    {}

    void addDamage(Rect area)
    {}

    int savedArea() const {
      return 0;
    }

private:
    const int n;
    const int m;
};

void setupIO()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

void process(std::istream& in, std::ostream& out)
{
    int n, m, q;

    in >> n >> m >> q;
    City city{n, m};
    while (q--) {
      Rect damageArea;
      in >> damageArea;
      city.addDamage(damageArea);
    }
    out << city.savedArea();
}

int main()
{
    setupIO();
    process(std::cin, std::cout);
}

Zastanów się czy nie można to zrobić lepiej niż używając tej wielkiej macierzy.
Kodu będzie dużo więcej, ale będie szybszy, bo nie będziesz musiał malować po pamięci jak prostokąt będzie duży.

Zeby zrobic w qm(log(n)) lub qn(log(m)) wystarczy zadanie sprowadzic do wersji 1-wymiarowej i n lub m razy dodawac lub laczyc zakresy.

Wystarczy zapytać chatbota po co się męczyć:

ja:

Napisz program w C++ rozwiązujący poniższy problem:

Stolica Bajtocji jest aktualnie bombardowana, a do centrum dowodzenia napływają informacje o zniszczeniach.
Terytorium Bajtocji można przedstawić na mapie jako prostokąt o wymiarach n na m i wierzchołkach w punktach (0, 0), (n, 0), (n, m), (0, m).
Każda informacja o zniszczeniu składa się z czterech liczb całkowitych x1, y1, x2, y2, oznaczających, że prostokątny obszar o przeciwległych wierzchołkach w punktach (x1, y1), (x2, y2) został zbombardowany, a w efekcie całkowicie zniszczony. Twoim zadaniem jest podać ile km2 Bajtocji zdołało ostatecznie ocaleć.
Wejście:
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite n, m, q (1 <= n, m <= 10^3, 1 <= q <= 10^6), oznaczające odpowiednio wymiary Bajtocji i liczbę raportów o zniszczeniach.
W kolejnych q wierszach znajdują się opisy zniszczeń, składające się z liczb całkowitych x1, y1, x2, y2 (x1 < x2, y1 < y2, 0 <= x1, x2 <= n, 0 <= y1, y2 <= m), oznaczających, że prostokątny obszar o wierzchołkach w punktach (x1, y1), (x2, y2) został całkowicie zniszczony.
Wyjście:
Należy wypisać jedną liczbę całkowitą - powierzchnię ocalałego obszaru

chatGPT:

#include <iostream>
using namespace std;

const int MAX = 1003;

int n, m, q, x1, y1, x2, y2, area = n * m;
bool map[MAX][MAX];

int main() {
    cin >> n >> m >> q;
    area = n * m;
    for (int i = 0; i < q; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        for (int x = x1; x < x2; x++) {
            for (int y = y1; y < y2; y++) {
                if (!map[x][y]) {
                    map[x][y] = true;
                    area--;
                }
            }
        }
    }

    cout << area << endl;
    return 0;
}

Ten program rozwiązuje problem, otrzymując dane wejściowe z pierwszego wiersza standardowego wejścia (wymiary Bajtocji i liczbę raportów o zniszczeniach), a następnie pobierając dane z kolejnych q wierszy wejścia (opisujące zniszczenia). Tworzy mapę Bajtocji jako tablicę dwuwymiarową bool map[MAX][MAX], gdzie MAX jest stałą oznaczającą maksymalny rozmiar mapy. W pętli for jest iterowane przez liczbę raportów o zniszczeniach, pobierając x1, y1, x2, y2 z wejścia i oznaczając obszar jako zniszczony na mapie (map[x][y] = true).

Jeśli obszar jest oznaczony jako zniszczony pierwszy raz, zmniejsza się zmienna area o 1. Po zakończeniu pętli program wyświetla liczbę całkowitą - powierzchnię ocalałego obszaru.

ja:

zoptymalizuj ten program używając sum prefiksowych

chatGPT:

#include <iostream>
using namespace std;

const int MAX = 1003;

int n, m, q, x1, y1, x2, y2, area = 0;
int map[MAX][MAX];

int main() {
    cin >> n >> m >> q;
    area = n * m;

    for (int i = 0; i < q; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        map[x1][y1]++;
        map[x2][y2]++;
        map[x1][y2]--;
        map[x2][y1]--;
    }

    for (int x = 0; x < n; x++) {
        for (int y = 0; y < m; y++) {
            map[x][y] += map[x - 1][y] + map[x][y - 1] - map[x - 1][y - 1];
            if (map[x][y])
                area--;
        }
    }

    cout << area << endl;
    return 0;
}

Ten program rozwiązuje problem używając sum prefiksowych. Tworzy mapę Bajtocji jako tablicę dwuwymiarową int map[MAX][MAX], gdzie MAX jest stałą oznaczającą maksymalny rozmiar mapy. W pętli for jest iterowane przez liczbę raportów o zniszczeniach, pobierając x1, y1, x2, y2 z wejścia i zwiększając map[x1][y1] oraz map[x2][y2], a następnie zmniejszając map[x1][y2] oraz map[x2][y1].

Następnie program iteruje po całej mapie, sumując map[x][y] z map[x-1][y] + map[x][y-1] - map[x-1][y-1] i jezeli map[x][y] jest różne od 0 area--;

Po zakończeniu pętli program wyświetla liczbę całkowitą - powierzchnię ocalałego obszaru.

czy nauka algorytmów ma jeszcze sens?
nie wiem tylko czemu MAX=1003 ale pewnie błędnie uznało że 10^3 to 1003

w sumie rozwiązanie banalne jak już się je widzi

//
Kazałem mu jeszcze zoptymalizować pod kątem pamięci ale zaczęło wypluwać nieprawidłowe kody z jednowymiarową tablicą, w końcu się zakręciło w miejscu i stwierdziło że lepiej będzie na dwuwymiarowej i wypluło z powrotem powyższy kod.
// edit 2:
nie jednak nie stwierdziło że 10^3 to 1003 bo podając mu 1000000 podstawił 1000003. widocznie uważa że dodanie 3 jest w dobrym guście. A może to taki watermark AI żeby nie oszukiwać na konkursach algorytmicznych?

obscurity napisał(a):

Wystarczy zapytać chatbota po co się męczyć:

No a ja widzę w tym kodzie UB, już przy pierwszej iteracji liczącej ostateczny wynik.

Jest sens się uczyć algorytmów oraz optymalizacji, bo generalnie musisz wiedzieć czego chcesz, aby o to poprosić bota i umieć sprawdzić czy to się nadaje

Dobrze myslisz, można użyć sum prefiksowych ale 2d https://platform.meetit.pl/articles/pod_pre