past2n

NISHIO Hirokazu [Translate]
PAST2N
N - ビルの建設

from 第二回 アルゴリズム実技検定
PAST2N
考えたこと
ある点について50000件の正方形の中からそれを含むものを見つけてコストを加算する
ただし線形オーダーでは間に合わない
どうするか
1次元だったら累積和の変動ポイントを記録しといて二分探索なのだが、今回は二次元だ
2次元いもす法かな？
座標圧縮しても10^5なので二次元でやるのは無理っぽい
公式解説
平面走査法
改めて考えたこと
長方形区間add
これはクエリの先読みが必要かな
クエリごとにN件の正方形の処理をしたら個別の処理がどんなに速くても間に合わない
区間の境界線も含むので混ぜて(y, x)でソート
実装
セグメント木を作ろうとして気づいた
値の範囲が10^9→座標圧縮必要
RangeAddは二つのPointAdd
RangeAddとReadが同じ座標で重なった時「正方形の角も正方形の内側」という仕様なので、開始のRangeAddはReadより先に処理されなければならない。
逆に終了のRangeAddは後に処理されなければならない
座標を0.5ずらそう
サンプル1は通ったのにサンプル2で負の値が出てきた
→座標圧縮したのにセグメント木に元の座標でアクセスしてたミス
AC
pythondef solve(N, Q, SS, QS):
    xs = []
    for x, _, width, _ in SS:
        xs.append(x)
        xs.append(x + width)
    for x, _ in QS:
        xs.append(x)
    xs.sort()
    x2i = {}
    for i, x in enumerate(xs):
        x2i[x] = i
    i2x = xs

    commands = []
    for x, y, width, cost in SS:
        start = x2i[x]
        end = x2i[x + width]
        commands.append((
            y, start - 0.5,
            "add",
            start, end, cost
        ))
        commands.append((
            y + width, end + 0.5,
            "add",
            start, end, -cost
        ))
    for x, y in QS:
        commands.append((
            y, x2i[x],
            "read",
            None, None, None
        ))
    commands.sort()
    result = {}

    # segtree
    from operator import add
    set_width(len(x2i) + 10)
    table = [0] * SEGTREE_SIZE
    for y, x, typ, start, end, cost in commands:
        if typ == "add":
            # range add as two point_add
            point_set(table, start, get_value(table, start) + cost, add)
            point_set(table, end + 1, get_value(table, end + 1) - cost, add)
        else:
            # point read as range sum
            v = range_reduce(table, 0, x + 1, add, 0)
            result[(i2x[x], y)] = v

    # print answer
    for q in QS:
        print(result[q])