sumy prefiksowe

Question

Siemka, dostałem zadanie na poćwiczenie struktur danych. Spróbowałem je zrobić na tablicę, lecz program jest zbyt wolny.

zadanie: link

mój kod:

#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;
}

 

Comments

Można rozwiązać drzewem przedziałowym 2d, ale to prawdopodobnie wciąż byłoby za wolne.

Hint: sumy prefiksowe

---

nie widze powiazania, mozesz jeszcze troszeczke podpowiedziec?

---

jakbyś rozwiązał ten problem ale w 1d? Masz tablice rozmiaru n, na której bombardujesz kolejne przedziały. Ile pól nigdy nie zostało zbombardowanych?

---

miałeś na myśli talice rozmiaru n * m?

ale to i tak zajmie dużo czasu, bo co jeśli np ktoś będzie bombardował ciągle te same przedziały?

---

Nie, tablica 1d rozmiaru n (n <= 1e6). Na razie spróbuj rozwiązać ten prostszy przypadek i zobacz jak go uogólnić dla 2d.

---

Jesli bombardujesz przedział [l, r] dodajesz 1 do arr[l], i odejmujesz -1 od arr[r+1] i na tym liczysz sume prefiksową. Jak teraz policzyć ile pól nie zostało zbomardowanych?

---

juz zaczynam widzieć szybkość i prostotę tego podejścia, tylko po co mieszać z indeksami, tzn arr[r + 1 (a nie od r)].

---

Jak dodasz 1 do arr[l] i odejmiesz 1 od arr[r] to pominiesz jedno bombardowanie (bombardowanie pola r).