はまやんはまやんはまやん

hamayanhamayan's blog

Building Construction [第二回 アルゴリズム実技検定 N]

競技プログラミング

https://atcoder.jp/contests/past202004-open/tasks/past202004_n

前提知識

解説

https://atcoder.jp/contests/past202004-open/submissions/12901572

二次元imosを拡張させて解く。
二次元imosが分からない場合はそちらを先に勉強した方が、こちらに取り組みやすいだろう。
さて、二次元imos的には、各領域に対して、
(xmin, ymin) +C
(xmin+D+1, ymin) -C
(xmin, ymin+D+1) -C
(xmin+D+1, ymin+D+1) +C
として、縦に累積和、横に累積和をしたときの(A[j],B[j])がそのまま答えになる。
だが、横と縦に累積和は盤面が大きすぎてできないので、何とかする必要がある。
二次元imosを行うと、すべてのマスについてコストが分かるが、今回はそこまでは必要ない。
指定したマスについてコストが分かればいい。
この時、指定したマス(A[j],B[j])のコストは、
二次元imosの前処理をした状態で(0,0)と(A[j],B[j])を対角点とする長方形に含まれる
コストの総和と等しくなる。
なので、二次元に対する矩形和が取れれば今回の問題は解けることになる。

ここから解法が2択あって、「2Dセグメントツリー」か「平面走査」のどちらかである。
まず、どちらであっても使用する座標をすべて洗い出して座標圧縮しておこう。

平面走査は割と古典的（なイメージ）だが強力である。
BITを持って、y座標を小さい方を順番に見ていって、縦の累積和をやりながら、
実際に求めるときは横の累積和の代わりにBITを使うことで、(0,0)からの矩形和を求めるという戦略。

2Dセグメントツリーを仮に持っていれば、今回要求されている操作と行える操作が等しいので、分かりやすい。
計算量がやや心配だが、ちょっとだけ実行時間制限も大きいので、使ってもいいよというメッセージだろう。

int N, Q;
int xmin[50101], ymin[50101], D[50101], C[50101];
int A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> xmin[i] >> ymin[i] >> D[i] >> C[i];
    rep(i, 0, Q) cin >> A[i] >> B[i];

    vector<int> xs, ys;
    rep(i, 0, N) {
        xs.push_back(xmin[i]);
        xs.push_back(xmin[i] + D[i] + 1);
        ys.push_back(ymin[i]);
        ys.push_back(ymin[i] + D[i] + 1);
    }
    rep(i, 0, Q) {
        xs.push_back(A[i]);
        ys.push_back(B[i]);
    }

    sort(all(xs));
    xs.erase(unique(all(xs)), xs.end());
    sort(all(ys));
    ys.erase(unique(all(ys)), ys.end());

    int NY = ys.size();
    vector<vector<pair<int, ll>>> v(NY);
    vector<map<int, ll>> v2(NY);
    rep(i, 0, N) {
        int xm = lower_bound(all(xs), xmin[i]) - xs.begin();
        int xmd = lower_bound(all(xs), xmin[i] + D[i] + 1) - xs.begin();
        int ym = lower_bound(all(ys), ymin[i]) - ys.begin();
        int ymd = lower_bound(all(ys), ymin[i] + D[i] + 1) - ys.begin();

        v2[ym][xm] += C[i];
        v2[ymd][xm] -= C[i];
        v2[ym][xmd] -= C[i];
        v2[ymd][xmd] += C[i];
    }
    rep(y, 0, NY) fore(p, v2[y]) v[y].push_back(p);

    StaticHealthy2DSegTree st;
    st.init(v);

    rep(i, 0, Q) {
        int x = lower_bound(all(xs), A[i]) - xs.begin();
        int y = lower_bound(all(ys), B[i]) - ys.begin();

        ll ans = st.get(0, y + 1, 0, x + 1);
        printf("%lld\n", ans);
        
    }
}