Sau đây mình xin chia sẻ lời giải của mình cho bài toán này. Nếu có sai sót, các bạn hãy comment ở dưới giúp mình 😃

Subtask 1 và 4:

Cả hai subtask này đều rất dễ, ta chỉ cần dùng một mảng đánh dấu hai chiều để đánh dấu những ô được tô màu, sau đó tính tổng những ô không được tô màu còn lại.

int main() {
    cin >> n >> m >> k ;
    while(k --) {
        cin >> x >> y >> u >> v ;
        for(ll i = x; i <= u; i ++) {
            for(ll j = y; j <= v; j ++) b[i][j] = 1 ;
        }
    }
    for(ll i = 1; i <= n; i ++) {
        for(ll j = 1; j <= m; j ++) {
            if(!b[i][j]) res = (res + (i * j)) % mod ;
        }
    }
    cout << res ;
}

Tuy nhiên cách này không thể áp dụng cho những trường hợp \(N\), \(M\) lớn, vì nó sẽ vượt quá giới hạn bộ nhớ và thời gian.
Độ phức tạp: \(O(N * M)\)

Subtask 2 và 3:

Trừ hai subtask trên, các subtask còn lại có \(N, M\) lớn, vậy nên ta không thể dùng hai vòng for lồng nhau để tính như cách trên được mà chỉ có thể tính trong độ phức tạp \(O(1)\).
Công thức tính tổng các ô trong hình chữ nhật có ô trái trên \((x, y)\) và ô phải dưới \((u, v)\) là:
\([x + (x + 1) + … + (u - 1) + u][y + (y + 1) + … + (v - 1) + v]\)
\((= [u(u + 1) / 2 + (x - 1)x / 2][v(v + 1) / 2 + (y - 1)y / 2])\)

Công thức này rất dễ để có thể tự suy ra được.
Từ đó ta viết hàm \(f(l, r)\) để tính tổng các số từ \(l\) đến \(r\):

ll f(ll l, ll r) {
    return ((r * (r + 1) / 2) % mod - (l * (l - 1) / 2) % mod + mod) % mod ;
}

Khi đã có được hàm \(f(l, r)\), ta sẽ viết tiếp một hàm để tính tổng các ô trong hình chữ nhật có ô trái trên \((x, y)\) và ô phải dưới \((u, v)\) theo công thức mình đã nói ở trên:

ll sum(ll x, ll y, ll u, ll v) {
    return f(x, u) * f(y, v) ;
}

Bây giờ, ta sẽ tính tổng của hình chữ nhật như đề đã cho, sau đó trừ cho tổng của phần hình chữ nhật được tô màu:

int main() {
    cin >> n >> m >> k ;
    kq = sum(1, 1, n, m) ;
    cin >> x >> y >> u >> v ;
    kq = ((kq - sum(x, y, u, v)) % mod + mod) % mod ;
    cout << kq ;
}

Lưu ý: Cần xử lý để tránh trường hợp kết quả là số âm.
Độ phức tạp: \(O(1)\)

Subtask 5 và 6:

Với subtask này, ta sẽ áp dụng cách làm giống với subtask 2 và 3. Có thể thấy, các subtask ở trên có \(K = 1\). Nhưng với các subtask còn lại có \(2 <= K <= 10\). Vì vậy \(K\) hình chữ nhật được chọn tô màu có thể đè lên nhau, nên khi trừ tổng trong các chữ nhật đó, ta có thể trừ nhầm thêm phần giao của chúng, dẫn đến bị kết quả sai.

Thật vậy. Xét test ví dụ của đề bài, ta thấy hai hình chữ nhật có phần giao là ô \((3, 2)\). Nếu dùng đúng cách trên, đáp án của ta sẽ bị trừ thêm \(6\) (giá trị của ô \((3, 2)\)). Vậy nên chúng ta cần cộng thêm phần giao của hai hình chữ nhật đó.

Để làm được như vậy, chúng ta cần viết được một hàm tính phần giao của hai hình chữ nhật. Các bạn có thể đọc code sau đây để hiểu hơn:

void intersect(ll x1, ll y1, ll u1, ll v1, ll x2, ll y2, ll u2, ll v2) {
    ll AnsX, AnsY, AnsU, AnsV ;
    if(u1 < x2 || u1 < x1) return ;
    if(u1 < y2 || v1 < y1) return ;
    AnsX = max(x1, x2) ;
    AnsU = min(u1, u2) ;
    AnsY = max(y1, y2) ;
    AnsV = min(v1, v2) ;
    kq = (kq + sum(AnsX, AnsY, AnsU, AnsV)) % mod ;
}

Phần còn lại chúng ta vẫn sẽ áp dụng như subtask 2 và 3:

int main() {
    cin >> n >> m >> k ;
    kq = sum(1, 1, n, m) ;
    for(ll i = 1; i <= k; i ++) {
        cin >> x[i] >> y[i] >> u[i] >> v[i] ;
    }
    kq = ((kq - sum(x[1], y[1], u[1], v[1])) % mod + mod) % mod ;
    kq = ((kq - sum(x[2], y[2], u[2], v[2])) % mod + mod) % mod ;
    intersect(x[1], y[1], u[1], v[1], x[2], y[2], u[2], v[2]) ; 
    cout << kq ;
}

Độ phức tạp: \(O(K)\)

Subtask 7 và 8:

Đây là hai subtask khó nhất trong bài, đặc biệt là subtask cuối. Để AC được subtask này, ta vẫn sẽ áp dụng như hai subtask 5 và 6.

Nhưng ở đây \(K <= 10\), vậy nên sẽ có thể có phần giao của nhiều hơn 2 hình chữ nhật được tô màu mà giá trị của chúng bị trừ nhiều lần. Để tính các phần giao đó, ta cần chọn ra các hình chữ nhật được tô màu và tính tổng phần giao của chúng.

Dùng thuật toán quay lui là lựa chọn tối ưu. Ta dùng một mảng đánh dấu b lưu lại những lựa chọn các hình chữ nhật: \(b[i] = 1\) nếu hình chữ nhật thứ i được lựa chọn và ngược lại \(b[i] = 0\):

void dequy(ll i) {
    if(i > k) kt() ;
    else {
        dequy(i + 1) ;
        b[i] = 1 ;
        dequy(i + 1) ;
        b[i] = 0 ;
    }
}

Chúng ta sẽ viết hàm \(kt()\) để kiểm tra tổng các giá trị trong phần giao của các hình chữ nhật được chọn và thực hiện công thức bao hàm loại trừ. Các bạn có thể tìm hiểu về bao hàm loại trừ ở đây. Trong subtask này, ta sẽ biến đổi hàm intersect ở trên thành hàm trả về giá trị bool: Hàm sẽ trả về \(0\) nếu hai hình chữ nhật trong hàm không có phần giao, ngược lại sẽ trả về \(1\), đồng thời tính luôn phần giao của hai tập hợp đó. Ta sẽ dùng \(4\) biến toàn cục để lưu kết quả của hàm.

Đây là hàm intersect sau khi ta viết lại:

bool intersect(ll x1, ll y1, ll u1, ll v1, ll x2, ll y2, ll u2, ll v2) {
    if(u1 < x2 || u2 < x1) return 0 ;
    if(v1 < y2 || v2 < y1) return 0 ;
    X = max(x1, x2) ;
    U = min(u1, u2) ;
    Y = max(y1, y2) ;
    V = min(v1, v2) ;
    return 1 ;
}

\(4\) biến toàn cục lưu lại kết quả của hàm là \(X, Y, U, V\).

Đây là hàm \(kt()\):

void kt() {
    X = 1, Y = 1, U = n, V = m ;
    ll cnt = 0 ;
    for(ll i = 1; i <= k; i ++) {
        if(b[i] == 0) continue ;
        cnt ++ ;
        if(!intersect(x[i], y[i], u[i], v[i], X, Y, U, V)) return ;
    }
    ll t = sum(X, Y, U, V) % mod ;
    if(cnt % 2 == 1) kq = ((kq - t) % mod + mod) % mod ;
    else kq = (kq + t) % mod ;
}

Khi đã viết được các hàm cần thiết, ta chỉ cần viết hàm main nữa là hoàn tất chương trình 😄😄😄
Độ phức tạp: \(O(2^K * K)\)
Các bạn có thể tham khảo code mình tại đây