C - Nuske vs Phantom Thnook

C - Nuske vs Phantom Thnook

解法

木の数は頂点-辺の数らしい

ので、二つを二次元累積和で持てばいい

しかし、辺の数を二次元累積和で計算すると赤と緑の分答えが大きくなってしまうので、「dh[i][h] :=  列i-1とiの間がhまでで繋がっている量」のようにして後で引いてやる

Submission #4639141 - AtCoder Grand Contest 015

struct RectangleSum {
    vector<vector<ll>> dat;
    int H, W;
    bool notBuild = true;

    RectangleSum(int H_, int W_) : dat(H_ + 1, vector<ll>(W_ + 1, 0)), H(H_), W(W_) {}

    void add(int h, int w, ll v = 1) {
        if (!notBuild)throw std::exception();
        h++, w++;
        if (h > H || w > W || h <= 0 || w <= 0)return;
        dat[h][w] += v;
    }

    void build() {
        notBuild = false;
        for (int i = 1; i <= H; ++i) {
            for (int j = 1; j <= W; ++j) {
                dat[i][j] += dat[i - 1][j] + dat[i][j - 1] - dat[i - 1][j - 1];
            }
        }
    }

    ll sum(int sy, int gy, int sx, int gx) {
        if (gx > W || gy > H) return 0;
        if (sx < 0 || sy < 0) return 0;
        if (sy >= gy || sx >= gx) return 0;
        if (notBuild)build();
        int res = dat[gy][gx] - dat[sy][gx] - dat[gy][sx] + dat[sy][sx];
//        deb(sy, gy, sx, gx);
//        deb(dat);
//        deb(res);
        return res;
    }
};


void solve() {
    in(H, W, q);
    nt(ba, H, W);
    minu(ba, '0');
    RectangleSum rv(H, W);
    RectangleSum re(H, W);
    rep(h, H) {
        rep(w, W) {
            if (!ba[h][w])con;
            rv.add(h, w);
            if (h && ba[h - 1][w]) {
                re.add(h, w, 1);
            }
            if (w && ba[h][w - 1]) {
                re.add(h, w, 1);
            }
        }
    }
    //dhはw指定
    vvi(dh, W, H + 1);
    vvi(dw, H, W + 1);
    rep(w, 1, W) {
        //1 index
        rep(h, H) {
            dh[w][h + 1] += dh[w][h];
            dh[w][h + 1] += (ba[h][w - 1] && ba[h][w]);
        }
    }
    rep(h, 1, H) {
        //1 index
        rep(w, W) {
            dw[h][w + 1] += dw[h][w];
            dw[h][w + 1] += (ba[h - 1][w] && ba[h][w]);
        }
    }
    while (q--) {
        dind(u, l, d, r);
        int sv = rv.sum(u, d + 1, l, r + 1);
        int se = re.sum(u, d + 1, l, r + 1);
        int mh = dh[l][d + 1] - dh[l][u];
        int mw = dw[u][r + 1] - dw[u][l];
        cout << sv - (se - mh - mw) << endl;
    }
}