ハンコ [codeFlyer （bitFlyer Programming Contest）D]

https://beta.atcoder.jp/contests/bitflyer2018-qual/tasks/bitflyer2018_qual_d

考察

1. 全探索対象を探す
2. マス目1つ1つで全探索すると10^6くらいなので、ここで全探索？
3. マス1つに対してできる操作を考えてみる
4. マスが#であれば、紙に長方形が出来上がる
5. 押された紙の完成形は#の個数と同じ個数の同じ形の長方形の重ね合わせになる
6. 紙が小さければ二次元imosでできる
7. 座圧でimosのパターンか？
8. それでいけそう

前提知識

• 二次元imos
• 座標圧縮

解説

https://beta.atcoder.jp/contests/bitflyer2018-qual/submissions/2598933

二次元imosと座圧（座標圧縮）が分からないと確実に解けない。
そちらをまず学習してから取り組もう。
　
ハンコの(x,y)が#であれば、紙の上に端が(x,y),(W-M+x,H-N+y)である長方形が描かれる。
紙が問題文の制約より小さければ、普通に二次元imosを使えば、黒に塗られているマスの個数が得られる。
座標がとても大きくなる可能性があるので、imosで使われる座標のx,y座標を座圧しよう。
座圧した後に二次元imosを行い、黒く塗られている面積を座圧を復元しながら足し合わせていくと答え。

int H, W, N, M;
string A[1010];
int B[2010][2010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> N >> M;
    rep(i, 0, N) cin >> A[i];
 
    vector<int> xdic, ydic;
    rep(y, 0, N) rep(x, 0, M) {
        xdic.push_back(x);
        xdic.push_back(W - M + x + 1);
        ydic.push_back(y);
        ydic.push_back(H - N + y + 1);
    }
    sort(all(xdic));
    xdic.erase(unique(all(xdic)), xdic.end());
    sort(all(ydic));
    ydic.erase(unique(all(ydic)), ydic.end());
 
    rep(sy, 0, N) rep(sx, 0, M) if (A[sy][sx] == '#') {
        int tx = W - M + sx + 1;
        int ty = H - N + sy + 1;
 
        int x1 = lower_bound(all(xdic), sx) - xdic.begin();
        int x2 = lower_bound(all(xdic), tx) - xdic.begin();
        int y1 = lower_bound(all(ydic), sy) - ydic.begin();
        int y2 = lower_bound(all(ydic), ty) - ydic.begin();
 
        B[y1][x1]++;
        B[y2][x1]--;
        B[y1][x2]--;
        B[y2][x2]++;
    }
 
    rep(y, 0, 2010) rep(x, 1, 2010) B[y][x] += B[y][x - 1];
    rep(x, 0, 2010) rep(y, 1, 2010) B[y][x] += B[y - 1][x];
 
    int xn = xdic.size();
    int yn = ydic.size();
 
    ll ans = 0;
    rep(sy, 0, yn - 1) rep(sx, 0, xn - 1) {
        int ty = sy + 1;
        int tx = sx + 1;
 
        int x1 = xdic[sx];
        int x2 = xdic[tx];
        int y1 = ydic[sy];
        int y2 = ydic[ty];
 
        ll dx = x2 - x1;
        ll dy = y2 - y1;
 
        if(B[sy][sx]) ans += dx * dy;
    }
 
    cout << ans << endl;
}