Checkered Stamps [「みんなのプロコン 2019」決勝 C]

https://atcoder.jp/contests/yahoo-procon2019-final/tasks/yahoo_procon2019_final_c

前提知識

• SegTree＋平面走査

解説

https://atcoder.jp/contests/yahoo-procon2019-final/submissions/4363922

こういう矩形クエリについて答える典型として「SegTree＋平面走査」がある。
それを理解してから本問題に取り組むことを勧める。
Fortune Tellingという問題があり、この問題の解法が理解できていれば、この問題を解くのは難しくない。
ちなみに、Fortune Tellingを理解するには座標圧縮に対応した遅延評価セグメントツリーを構築できる必要がある。
なので、「座標圧縮→遅延評価セグメントツリー→座標圧縮に対応した遅延評価セグメントツリー→SegTree＋平面走査」で学習しよう。
Fortune Tellingの方は解説もしっかりあるので、そちらで勉強しよう。
　
Fortune Tellingで得られる解法は「矩形flip, 全体sumのデータ構造」である。
下のコードではImos2DPreLoadingQueryAllGetでそれを実装してある。
これを使えば、この問題も解答できる。
　
まず、盤面を(x%2,y%2)で4領域に分割する。
市松模様でflipするというのは、分割後の領域のうち2つの領域をflipすることになる。
(R, C)ならば(R%2, C%2)と(1-R%2, 1-C%2)の領域の対応する領域をflipするということになる。
これで全体のflipを各領域のflipに変換すれば、最後に4領域の1の個数の総和が答えになっている。

Imos2DPreLoadingQueryAllGet<ll, 1 << 18> imos[2][2];
int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int h, w, y, x;
        cin >> h >> w >> y >> x;
        x--; y--;
        
        int ax = (x + 1) / 2;
        rep(px, 0, 2) rep(py, 0, 2) {
            if (x % 2 == px and y % 2 != py) continue;
            if (x % 2 != px and y % 2 == py) continue;
 
            int sx = (x - px) / 2;
            if (x - px < 0) sx = 0;
            else if ((x - px) % 2 != 0) sx++;
            int sy = (y - py) / 2;
            if (y - py < 0) sy = 0;
            else if ((y - py) % 2 != 0) sy++;
 
            int tx = (x + w - 1 - px) / 2;
            int ty = (y + h - 1 - py) / 2;
 
            if (sx <= tx and sy <= ty) imos[px][py].add(sx, sy, tx, ty);
        }
    }
 
    ll ans = 0;
    rep(px, 0, 2) rep(py, 0, 2) ans += imos[px][py].solve();
    cout << ans << endl;
}