読者です 読者をやめる 読者になる 読者になる

今日の典型データ構造4(解答編)

クエリ1で

(x0, y0) ~ (x1, y1)に+1

ではなく

(x0, y0), (x1, y1)に+1 (x0, y1), (x1, y0)に-1

にすれば

クエリ2は

"自分より左上の点の値のsum"というのを求めるクエリに変換できます

ここでこれを求めるためには

動的SegmentTreeに範囲sumができる平衡二分木を載せます。以上。

これでオンラインでも解けます。やったね