問題概要
$n$ 頂点の木が与えられる。頂点 $i$ には値 $c_i$ が割り当てられている。$m$ 個のクエリが以下の形式で与えられるので処理せよ。
1 x v: $c_x$ を $v$ で更新する。2 x l: 頂点 $x$ を根とする部分木を考える。$d = 0, 1, \dots ,l$ について、頂点 $x$ から深さ $d$ であるような頂点に書いてある値の和を $s_d$ とする。$s_0 \oplus s_1 \oplus \dots \oplus s_d$ ($\oplus$ は xor) を出力せよ。
制約
$n, m \leq 10^5, c_i \leq 10^9$
TL 4s
解法
一旦更新クエリを無視してみる。(小課題にもある) 木 DP をするとき、各深さについて、 $c_i$ の値の和の情報は欲しい。クエリに高速に答えることを考えると、深さに関する累積 XOR もあるとうれしい。ここで、深い方からの累積 XOR を全て保持する。するとマージテクが使えて全体で $O(n \log n)$ になる。普通浅い方から持つので、新鮮で面白かった。
あるクエリの前に更新クエリが $q$ 個あったら、 $O(q)$ 時間で更新クエリを考慮した答えに修正できる。このとき、更新クエリを代入ではなく加算だということにして前処理しておくと処理が簡単だった。
平方分割をして全体で $O((n + m) \sqrt m \log n)$ 時間。
更新クエリの処理で、部分木のチェックや深さのチェックなどをいれるので定数倍が心配に見えるが、ブロックサイズが $O(\sqrt m)$ であればこの部分は $O(n \sqrt m)$ なのでなんとかなる。オーダー上のボトルネックはマージテクのみで、これはそこまで重くない。
自分の実装
感想
JOI 10 レベルだと思う。春ならなんだかんだ 15 人くらいに解かれそう。
コメント