Get the Salary of Atcoder（square869120Contest #4 [G]）

概要

問題文 → ■
公式解説 → ■, p.86
自分の提出 → ■

解法

Euler Tour をとって、Euler Tour における頂点順を $x$ 座標、木における深さを $y$ 座標と見なすことで、次のクエリ処理に帰着できます：

• 矩形領域内のデータ点に対して、$v$ を加算する
• 矩形領域内のデータ点の値の総和を求める
• データ点を追加する

これが 1 次元の区間クエリだと、遅延セグメント木でできます。2 次元の矩形クエリでも、kd tree を用いると今回の矩形クエリを処理することができます。kd tree による矩形クエリは点の個数の $1/2$ 乗の時間計算量で行えて、本問題は $O(N+Q\sqrt{N+Q})$ 時間で解くことができます。

参考文献：https://trap.jp/post/1489/

kd tree による遅延伝播の verify 問題としてもちょうどいい気がします。