Subtask 1: ~h, w, n \leq 200~

Ta thực hiện cập nhật ~\mathcal{O}(n^2)~ cho mỗi truy vấn, sau đó dùng DFS hoặc DSU để xác định các thành phần liên thông.

Độ phức tạp: ~\mathcal{O}(n^3)~.

Subtask 2: ~h, w, n \leq 2000~

Để thao tác cập nhật có độ phức tạp tốt hơn, ta có thể dùng BIT2D, SegmentTree2D. Tuy nhiên bài toán chỉ cần ta có giá trị cuối cùng của ma trận sau $n$ truy vấn. Vì vậy ta có thể thực hiện như sau:

• Với mỗi thao tác cập nhật thêm một giá trị delta trên hình chữ nhật từ ô ~(left, bot)~ đến ô ~(right, top)~, ta cập nhật tại các ô sau trong ~\mathcal{O}(1)~:

    val[left][bot] += delta;
    val[left][top] -= delta;
    val[right][bot] -= delta;
    val[right][top] += delta;

• Sau khi thực hết các thao tác, ta cộng dồn ma trận trong ~\mathcal{O}(n^2)~ với công thức:

val[i][j] = val[i-1][j] + val[i][j-1] - val[i-1][j-1]

Sau đó ta có thể xử lí như subtask 1 để tìm đáp án.

Độ phức tạp: ~\mathcal{O}(n + n^2)~

Code tham khảo

// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;

/***Common Functions***/
template <class T>
bool minimize(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
bool maximize(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
void read(T &a) {
    a = 0;
    char c; 
    while (!isdigit(c = getchar())) {}
    do {
        a = a*10 + (c-'0');
    } while (isdigit(c = getchar()));
}

template<class T> 
void write(T a){
    if (a > 9) write(a/10);
    putchar(a%10 + '0');
}

/***End of Template***/
int height, width, numDays, K;
const int N = 2005;
struct Query {
    int type, bot, top, left, right;
    //mild: 0, rain: 1, sun: 2
} queries[N];
int val[N][N];
bool visited[N][N];
const int X[4] = {1, -1, 0, 0};
const int Y[4] = {0, 0, -1, 1};

void Input() {
    cin >> height >> width >> numDays >> K;
    FOR(i, 1, numDays) {
        string type; cin >> type;
        if (type == "mild") queries[i].type = 0;
        else {
            int t, b, l, r; cin >> l >> b >> r >> t;
            queries[i] = {(type == "sun")+1, b, t, l, r};
        } 
    }
}

bool valid(int i, int j) {
    return i >= 1 && i <= width && j >= 1 && j <= height;
}

int dfs(int i, int j) {
    if (abs(val[i][j]) > K) return 0;
    visited[i][j] = true;
    int ans = 1;
    FOR(dir, 0, 3) {
        int x = i + X[dir], y = j + Y[dir];
        if (valid(x, y) && !visited[x][y]) ans += dfs(x, y);
    }
    return ans;
}

void Solve() {
    memset(val, 0, sizeof val);
    FOR(i, 1, numDays) if (queries[i].type != 0) {
        int delta = queries[i].type == 1 ? 1 : -1;
        val[queries[i].left][queries[i].bot] += delta;
        val[queries[i].left][queries[i].top+1] -= delta;
        val[queries[i].right+1][queries[i].bot] -= delta;
        val[queries[i].right+1][queries[i].top+1] += delta;
    }
    FOR(x, 1, width) FOR(y, 1, height) {
        val[x][y] += val[x-1][y] + val[x][y-1] - val[x-1][y-1];
    }
    int cnt = 0;
    int total = 0;
    FOR(i, 1, width) FOR(j, 1, height) if (abs(val[i][j]) <= K && !visited[i][j]) {
        total += dfs(i, j);
        cnt++;
    }
    cout << total << ' ' << cnt;
}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("inputf.in", "r")) freopen("inputf.in", "r", stdin);
    Input(), Solve();
    return 0;
}

Subtask 3: ràng buộc gốc

Với kích thước ma trận lớn, ta không thể biểu diễn thành mảng hai chiều được. Tuy nhiên, do số lượng truy vấn nhỏ (~\leq 2000~), ta có thể thực hiện nén ma trận. Ta dùng các chỉ số ~l, r+1~ làm các cột, các chỉ số ~b, t+1~ làm các hàng, giao giữa các cột và hàng sẽ tạo thành các ô quản lý một hình chữ nhật gồm nhiều ô trên ma trận gốc. Từ đây ta nhận thấy sau khi thực hiện các thao tác, các ô gốc trong hình chữ nhật được quản lý bởi các "ô mới" sẽ luôn có giá trị giống nhau. Nói cách khác, các truy vấn cập nhật sẽ luôn chứa "trọn" các hình chữ nhật này.

Với mỗi thao tác cập nhật, ta xác định "thứ tự" của các hàng và cột cần cập nhật trong ~\mathcal{O}(\log n)~ và cập nhật như bình thường. Sau đó, ta xác định các thành phần liên thông tương tự như các subtask trước. Lưu ý khi tính tổng số ô đất, ta phải nhân kích thước mà ô trên ma trận quản lý.

Độ phức tạp:

Code tham khảo

// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;

/***Common Functions***/
template <class T>
bool minimize(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
bool maximize(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
void read(T &a) {
    a = 0;
    char c; 
    while (!isdigit(c = getchar())) {}
    do {
        a = a*10 + (c-'0');
    } while (isdigit(c = getchar()));
}

template<class T> 
void write(T a){
    if (a > 9) write(a/10);
    putchar(a%10 + '0');
}

/***End of Template***/
int height, width, numDays, K;
const int N = 2e3+5;
struct Query {
    int type, bot, top, left, right;
    //mild: 0, rain: 1, sun: 2
} queries[N];
vi valX, valY;
int val[2*N][2*N];
bool visited[2*N][2*N];
const int X[4] = {1, -1, 0, 0};
const int Y[4] = {0, 0, -1, 1};

void Input() {
    cin >> height >> width >> numDays >> K;
    FOR(i, 1, numDays) {
        string type; cin >> type;
        if (type == "mild") queries[i].type = 0;
        else {
            int t, b, l, r; cin >> l >> b >> r >> t;
            queries[i] = {(type == "sun")+1, b, t, l, r};
        } 
    }
}

int getXId(int x) {
    return lower_bound(ALL(valX), x) - valX.begin();
}

int getYId(int y) {
    return lower_bound(ALL(valY), y) - valY.begin();
}

bool valid(int i, int j) {
    return i >= 0 && i < (int)valX.size()-1 && j >= 0 && j < (int)valY.size()-1;
}

ll getSize(int i, int j) {
    return 1ll*(valX[i+1]-valX[i])*(valY[j+1] - valY[j]);
}

ll bfs(int sX, int sY) {
    ll ans = getSize(sX, sY);
    queue<ii> q; q.push(mp(sX, sY));
    visited[sX][sY] = 1;
    while (q.size()) {
        int i, j; tie(i, j) = q.front(); q.pop();
        FOR(dir, 0, 3) {
            int x = i + X[dir], y = j + Y[dir];
            if (valid(x, y) && !visited[x][y] && abs(val[x][y]) <= K) {
                visited[x][y] = true;
                ans += getSize(x, y);
                q.push(mp(x, y));
            }
        }
    }
    return ans;
}

void Solve() {
    vi().swap(valX); vi().swap(valY);
    valX.pb(1), valX.pb(width+1);
    valY.pb(1), valY.pb(height+1);  
    FOR(i, 1, numDays) {
        if (queries[i].type == 0) continue;
        valX.pb(queries[i].left);
        valX.pb(queries[i].right+1);
        valY.pb(queries[i].bot);
        valY.pb(queries[i].top+1);
    }
    sort(ALL(valX)); valX.resize(unique(ALL(valX)) - valX.begin());
    sort(ALL(valY)); valY.resize(unique(ALL(valY)) - valY.begin());

    memset(val, 0, sizeof val);
    FOR(i, 1, numDays) if (queries[i].type != 0) {
        int delta = queries[i].type == 1 ? 1 : -1;
        int left = getXId(queries[i].left);
        int right = getXId(queries[i].right+1);
        int bot = getYId(queries[i].bot);
        int top = getYId(queries[i].top+1);

        val[left][bot] += delta;
        val[left][top] -= delta;
        val[right][bot] -= delta;
        val[right][top] += delta;
    }
    FOR(x, 0, (int)valX.size()-1) FOR(y, 0, (int)valY.size()-1) {
        if (x) val[x][y] += val[x-1][y];
        if (y) val[x][y] += val[x][y-1];
        if (x && y) val[x][y] -= val[x-1][y-1];
    }

    int cnt = 0;
    ll total = 0;
    FOR(i, 0, (int)valX.size()-2) FOR(j, 0, (int)valY.size()-2) if (abs(val[i][j]) <= K && !visited[i][j]) {
        total += bfs(i, j);
        cnt++;
    }
    cout << total << ' ' << cnt;
}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("inputf.in", "r")) freopen("inputf.in", "r", stdin);
    Input(), Solve();
    return 0;
}