# Bonus

Mỗi vùng liên thông chọn $1$ ô làm đại diện và đặt giá trị ô đó trên lưới bằng $1$, các ô còn lại đặt bằng $0$.

Với mỗi truy vấn:
- Tính tổng các ô $1$ nằm trong hình chữ nhật (HCN) của truy vấn đó (*)
- Các vùng liên thông thuộc HCN nhưng chưa thuộc (*) thì ô đại diện nằm bên ngoài HCN, ta có thể đếm các vùng này bằng cách xét các ô ở biên của HCN vì vùng liên thông đó phải cắt qua cạnh HCN.

Độ phức tạp: $O(Q \times (m+n))$

Code:

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;
const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};

int a[N][N], n, m, s[N][N], occ[N * N];
pair<int, int> p[N * N];
queue<pair<int, int>> que;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            if (!p[a[i][j]].first) {
                p[a[i][j]] = {i, j};
                s[i][j]++;
            }
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            s[i][j] += s[i - 1][j] +
            s[i][j - 1] - s[i - 1][j - 1];
    int q; cin >> q;
    for (int tim = 1; tim <= q; tim++) {
        int u, l, d, r;
        cin >> u >> l >> d >> r;
        int res = s[d][r] - s[d][l - 1]
        - s[u - 1][r] + s[u - 1][l - 1];
        int x, y;
        for (int i = u; i <= d; i++) {
            if (occ[a[i][l]] != tim) {
                occ[a[i][l]] = tim;
                tie(x, y) = p[a[i][l]];
                if (x < u || x > d
                || y < l || y > r)
                    res++;
            }
            if (occ[a[i][r]] != tim) {
                occ[a[i][r]] = tim;
                tie(x, y) = p[a[i][r]];
                if (x < u || x > d
                || y < l || y > r)
                    res++;
            }
        }
        for (int j = l; j <= r; j++) {
            if (occ[a[u][j]] != tim) {
                occ[a[u][j]] = tim;
                tie(x, y) = p[a[u][j]];
                if (x < u || x > d
                || y < l || y > r)
                    res++;
            }
            if (occ[a[d][j]] != tim) {
                occ[a[d][j]] = tim;
                tie(x, y) = p[a[d][j]];
                if (x < u || x > d
                || y < l || y > r)
                    res++;
            }
        }

        cout << res << '\n';
    }
}