CSES Forest Queries

題目連結

解題思路

如果使用暴力判斷，時間複雜度為 $O(n^2 \times q)$ ，不夠快。

這時，我們可以使用二維前綴和來優化這個計算，時間複雜度為 $O(n^2)$ 預處理、 $O(1)$ 回答每一次查詢，能在時限內通過。

更精確來說，因為我們要求一個區塊內有多少樹（*），可以將 * 的位置定義為 $1$（一棵樹），. 的位置定義為 $0$（零棵樹）。將字元改成數字以後，便可以用之前教過的方法求出前綴和。

定義陣列

vector<string> input(n);
...
vector<vector<int>> val(n, vector<int>(n));
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (input[i][j] == '*') {
            val[i][j] = 1;
        }
    }
}

預處理前綴和

vector<vector<int>> psum(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        psum[i][j] = psum[i - 1][j] + psum[i][j - 1] - psum[i - 1][j - 1] + val[i - 1][j - 1];
    }
}
        

註：因為此程式碼的 $val$ 二維陣列為 0-based，在處理前綴和的時候要在 $index$ 中多扣 $1$。

計算

使用二維前綴和陣列求出區塊和：

int sum = psum[y2][x2] - psum[y1 - 1][x2] - psum[y2][x1 - 1] + psum[y1 - 1][x1 - 1];

常見錯誤

0 / 1 based

請自己注意自己陣列定義及題目敘述的陣列 / 值是從 $0$ 開始還是從 $1$ 開始（通常題目都是 1-based）。

輸入順序

此題的輸入順序並非 x1, x2, y1, y2 或是 x1, y1, x2, y2，而是 y1, x1, y2, x2。實作的時候務必要多注意！

完整程式碼

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<string> input(n);
    for (int i = 0; i < n; i++) {
        cin >> input[i];
    }
    vector<vector<int>> val(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (input[i][j] == '*') {
                val[i][j] = 1;
            }
        }
    }
    vector<vector<int>> psum(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            psum[i][j] = psum[i - 1][j] + psum[i][j - 1] - psum[i - 1][j - 1] + val[i - 1][j - 1];
        }
    }
    for (int i = 0; i < q; i++) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        int sum = psum[y2][x2] - psum[y1 - 1][x2] - psum[y2][x1 - 1] + psum[y1 - 1][x1 - 1];
        cout << sum << "\n";
    }
}