CSES – Forest Queries

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 1005;
int n,q;
char maze[maxn][maxn];
vector<int> pre[maxn];
//
signed main(){
    fastio;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>maze[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        pre[i].push_back(0);
        for(int j=1;j<=n;j++){
            pre[i].push_back(pre[i].back() + (maze[i][j] == '*'));
        }
    }
    while(q--){
        int ans = 0;
        int a,b,c,d; cin>>a>>b>>c>>d;
        if(tie(a,b) > tie(c,d)) swap(a,c), swap(b,d);
        for(int i=a;i<=c;i++) ans += pre[i][d] - pre[i][b-1];
        cout<<ans<<"\n";
    }
    return 0;
}