/
最近
.rdf
追記
編集
設定
本棚
翌日へ
前日へ
脳
l
o
g
[
2
0
2
2
0
6
2
1
]
2
0
2
2
年
0
6
月
2
1
日
(
火
)
[
A
t
C
o
d
e
r
]
精進
。
A
B
C
1
8
7
-
E
「
T
h
r
o
u
g
h
P
a
t
h
」
(
水
d
i
f
f
)
。
コンテ
ス
ト当日に
2
5
分で
D
まで解いていながら残り
7
5
分で解けなか
った問題
。
翌日のふりかえり
>
2
0
2
1
0
1
0
3
p
0
1
。
「全然ル
ープの軸が見えなか
った
」
と書いてあるが
、
以前も今日
(
の最初
)
も問題の形式に引
っぱられて辺を中心としたル
ープしか考えられていなか
った
。
考えるのは頂点について
。
■仮に定めた木の根によ
って決まる親子関係とクエリの種類
(
t
)
によ
って
、
クエリは
、
a
か
b
を根とする部分木に
x
を加算するか
、
部分木以外に
x
を加算すると理解される
。
部分木に加算するのはオイラ
ーツア
ーと累積和の組み合わせでいけるし
、
部分木以外に加算するには全体に
x
を加算してから部分木を対象に
-
x
を足せばいい
。
■
提出
#
3
2
6
4
9
7
4
7
(
A
C
/
5
7
7
B
y
t
e
/
8
3
2
m
s
)
。
以前の日記
に
「筆塗りを思い出した
」
とも書いてあるから当時からオイラ
ーツア
ーは知
っていた
。
硬直した視点が解けなか
った唯一の理由
。
■
解説
を読めばオイラ
ーツア
ーはいらなか
った
。
それはクエリを処理しながら質問にも答えたいときに
B
I
T
を使
って累積和の構築を高速化する方法
。
解説の最後
に
「
また
、
各クエリで辺
e
以外では
c
a
i
−
c
b
i
の値が変わらないことに注目し
、
c
1
と
c
a
i
−
c
b
i
の値を管理しても同様に解くことができます
」
とも書いてあるけど
、
え
っと
、
よくわかりません
。
■
■
■木の全体を変化量
(
差分
)
の連鎖として見る
。
頂点の値は変化量の累積
。
変化量の累積は相対値なので木全体の値を一意に定めるアンカ
ー
(
初項
)
として
c
1
に代表させる
。
根
っこの値を代表値にすると都合がいいのは
、
親子関係で辺の向きが判別できるから
。
■
提出
#
3
2
6
5
1
1
3
6
(
A
C
/
4
0
8
B
y
t
e
/
9
5
8
m
s
)
。
時間もメモリ使用量もさ
っきの提出に劣
ってるのが納得いかない
。
いやまあ
、
判断と計算を先送りしたせいでややこしくて
、
判断と計算の材料を蓄えるために余計なメモリを使
ったんだろうなあとはわかる
。
報いがない
。
でも先送りせんと辺に注目してるのか頂点に注目してるのかわからんようになるのでしかたなか
った
。
解説の最後の１行
ってこういうことだと思
ったんだけど違うかな
。
翌日へ
前日へ