[ABC260G] Scalene Triangle Area题解

#include <iostream>

using namespace std;

const int MaxN = 2010;

int f[MaxN][MaxN], n, m, l, r, q, ans;
char c[MaxN][MaxN];

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> c[i][j], f[i][j] = f[i][j - 1] + (c[i][j] == 'O');
    }
  }
  for (cin >> q; q; q--) {
    cin >> l >> r, ans = 0;
    for (int i = max(l - m, 1); i <= l; i++) {
      int j = max(r - (m - (l - i)) * 2, 0);
      (j <= r) && (ans += f[i][r] - f[i][j]);
    }
    cout << ans << '\n';
  }
  return 0;
}

OXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX

111111000
111100000
110000000
000000000
……………………

1,0,0,0,0,0,-1,0,0
1,0,0,0,-1,0,0,0,0
1,0,-1,0,0,0,0,0,0
……………………

1,0,0,0,0,0,0,0,0
1,0,0,0,0,0,0,0,0
1,0,0,0,0,0,0,0,0
……………………

0,0,0,0,0,0,-1,0,0
0,0,0,0,-1,0,0,0,0
0,0,-1,0,0,0,0,0,0
……………………

1,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
-1,0,0,0,0,0,0,0,0
……………………

0,0,0,0,0,0,-1,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
1,0,0,0,0,0,0,0,0
……………………

#include <iostream>

using namespace std;

const int MaxN = 2010;

int n, m, t, l, r;
char c[MaxN][MaxN];
int q[MaxN * 3][MaxN], x[MaxN * 3][MaxN * 5], st[MaxN * 3][MaxN * 5];

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> c[i][j];
      if (c[i][j] == 'O') {
        q[i][j]++, q[i + m][j]--, x[i][j + 2 * m]--, x[i + m][j]++;
      }
    }
  }
  for (int i = 1; i <= n + m; i++) {
    for (int j = 1; j <= n + 2 * m; j++) {
      x[i][j] += x[i - 1][j + 2];
    }
  }
  for (int i = 1; i <= n + m; i++) {
    for (int j = 1; j <= n; j++) {
      q[i][j] += q[i - 1][j];
    }
  }
  for (int i = 1; i <= n + m; i++) {
    for (int j = 1; j <= n + 2 * m; j++) {
      st[i][j] = q[i][j] + x[i][j];
    }
  }
  for (int i = 1; i <= n + m; i++) {
    for (int j = 1; j <= n + 2 * m; j++) {
      st[i][j] += st[i][j - 1];
    }
  }
  for (cin >> t; t; t--) {
    cin >> l >> r;
    cout << st[l][r] << '\n';
  }
  return 0;
}