Forest Queries

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4signed main(){
5  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
6
7  int N, Q;
8  cin >> N >> Q;
9
10  int prefSum[N+1][N+1];
11  memset(prefSum, 0, sizeof prefSum);
12
13  for (int i = 1; i <= N; ++i) {
14    for (int j = 1; j <= N; ++j) {
15      char c; cin >> c;
16      prefSum[i][j] = prefSum[i-1][j] + prefSum[i][j-1] + (c == '*') - prefSum[i-1][j-1];
17    }
18  }
19
20  while (Q--) {
21    int i1, j1, i2, j2;
22    cin >> i1 >> j1 >> i2 >> j2;
23    cout << prefSum[i2][j2] - prefSum[i1-1][j2] - prefSum[i2][j1-1] + prefSum[i1-1][j1-1] << '\n';
24  }
25  return 0;
26}