操場上的莓果

分数： 100

时间限制： 1.0s

内存限制： 256M

作者：

happylittle7

题目类型

仔細看！這個男人太猛了！這位叫做美味莓果的男人，只用非常短的時間，就快把這個 Judge 上能解的題目解完了，身為平台出題者的快樂小 7 感到快樂充實且欣慰，要是這屆高一還有資電班的話，他絕對是難得一見的優秀人才。

快樂小 7 打算在操場上種一些莓果來慶祝，於是他在操場正中間開闢了一個大小為 \(n \times n\) 格的果園，並在每個格子中都埋了一個種子。

好不容易埋完後。他忽然發現有些格子他忘記把最重要的種子給埋進去，所以現在操場上有些格子實際上是空的。迷糊的小 7 想要重新再埋種子進去，但要一個一個找空格實在是太累了，於是他委託正在寫程式的你，希望能幫忙告訴他，果園裡指定的矩形範圍中，一共有幾個空格子。（健忘的他打算向你問 \(q\) 次）

小 7 每次詢問時會給你 \(2\) 個頂點座標 \((x_1, y_1)\) 和 \((x_2, y_2)\) ，請幫忙告訴他在以 \((x_1, y_1)\) 和 \((x_2, y_2)\) 為頂點所形成的矩形中，有幾個空格子。

輸入說明

第一行包含兩個正整數 \(n\) 和 \(q\)，分別表示正方形果園的邊長和小 7 詢問的次數，接下來 \(n\) 行每行有 \(n\) 個由.和*組成的字元，表示操場中間 \(n \times n\) 格的果園組成，.表示該格有種莓果，*表示該格是空的。另外為了方便管理，小 7 定義果園最左上方的格子座標為 \((1,1)\) ，最右下方的格子座標為 \((n,n)\)。

接下來 \(q\) 行，每行有 \(4\) 個正整數 \(y_1, x_1, y_2, x_2\) ，表示指定矩形範圍的其中兩個頂點座標。

\(1 \leq n \leq 1000\)
\(1 \leq q \leq 2 \times 10^5\)
\(1 \leq y_1 \leq y_2 \leq n\)
\(1 \leq x_1 \leq x_2 \leq n\)

輸出說明

對於每次詢問，請輸出果園指定矩形範圍中的空格子數量。

範例輸入1

4 4
.*..
*.**
**..
****
1 2 3 4
2 2 3 4
3 1 3 1
1 1 2 2

範例輸出1

YummyBerry 于2023年6月3日 6:41评论

前言

謝謝學長的誇獎以及量身定做的題目，我會繼續努力的(°ω°ฅ)

順便偷渡DC: Yummy Berry#3278 歡迎找我玩(╯✧∇✧)╯

題解

觀看題解前請先好好想過題目，觀看完題解後也想想為什麼這樣寫能AC，如果你因此寫出比我效率更好的程式就更棒了٩(◦`꒳´◦)۶。

這題明顯不能直接用迴圈算矩形內的空格子(TLE)。

因此我們要做預處理，可以發現空格子數量不會被改變。

所以此題只要利用 二維前綴和 即可。 https://walkonnet.com/archives/462481 <-關於前綴和的文章

然後有一點要注意的是題目是先給y再給x。

以下是程式碼。

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define sakura ios_base::sync_with_stdio(false), cin.tie(0);
using namespace std;

signed main(){
sakura
int n, q;
cin >> n >> q;

vector<vector<int>> pre(n+1, vector<int>(n+1, 0)); //多+1可以減少一點麻煩
for(int i = 1; i <= n; i++){
    string str;
    cin >> str;
    for(int j = 1; j <= n; j++){
        if(str[j-1] == '*'){
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + 1;
        }
        else{
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
        }
    }
}

while(q--){
    int y1, x1, y2, x2, ans;
    cin >> y1 >> x1 >> y2 >> x2;
    ans = pre[y2][x2] - pre[y2][x1-1] - pre[y1-1][x2] + pre[y1-1][x1-1];
    cout << ans << "\n";
}

return 0;
}