Good Bye 2015 C. New Year and Domino
C. New Year and Domino
問題
$h \times w$の盤面$h,w \le 500$が与えられる。 各マスは空白か障害物があるかのどちらかである。 以下のクエリが$q \le 10^5$個与えられるので答えよ。
- 座標$(t,l),(b,r)$が与えられる。盤面の中で、これらを頂点とする軸に並行な長方形の区間を考える。この区間中に、$1 \times 2$の長方形を置く置き方の総数を答えよ。
解法
累積和 + 包除原理。 ただし、区間からはみ出るように置く置き方を数えないように注意。
実装
累積和を3つに分けて持ってるの、もう少し上手くやれそうだなと感じる。
#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios::sync_with_stdio(false);
int h, w; cin >> h >> w;
vector<string> s(h); repeat (y,h) cin >> s[y];
vector<vector<int> > yacc(h+1, vector<int>(w+1));
vector<vector<int> > xacc(h+1, vector<int>(w+1));
vector<vector<int> > acc(h+1, vector<int>(w+1));
repeat (y,h) {
repeat (x,w) {
if (y+1 < h) yacc[y+1][x+1] += (s[y][x] == '.' and s[y+1][x] == '.');
if (x+1 < w) xacc[y+1][x+1] += (s[y][x] == '.' and s[y][x+1] == '.');
acc[y+1][x+1] = yacc[y+1][x+1] + xacc[y+1][x+1];
}
}
repeat (y,h) {
repeat (x,w) {
yacc[y+1][x+1] += yacc[y+1][x];
xacc[y+1][x+1] += xacc[y][x+1];
acc[y+1][x+1] += acc[y+1][x] + acc[y][x+1] - acc[y][x];
}
}
int queries; cin >> queries;
repeat (q, queries) {
int t, l, b, r; cin >> t >> l >> b >> r;
-- t; -- l;
cout << acc[t][l] - acc[t][r] - acc[b][l] + acc[b][r] - (yacc[b][r] - yacc[b][l]) - (xacc[b][r] - xacc[t][r]) << endl;
}
return 0;
}