問題 問題概要 オセロの向きを求める。 解法 一つずつやっていたらO(NQ)になるので、lとrの位置だけを記録してそれぞれの場所を何回ひっくり返されたかを記録すれば良い。ひっくり返された回数が、奇数であれば1、偶数であれば0である。区間に一様に1を加算…

問題 問題概要 (1)頂点vにxを加算し、その子に-xを加算し、またその子にxを加算する。 (2)頂点xの値を求める 解法 オイラーツアーで求めた順番で隣あうものは頂点の深さの差が1である。これを利用すれば、プラスマイナスの加算をsegtreeを2つ使って行うこと…

問題 問題概要 区間に対するクエリの問題。区間全体に対して、値を変更するため、遅延segment treeを使う。 解法 segtreeぽいな感はある。90度回転させてみるのは思いつかない。 解法は公式解説がわかりやすい。 https://tenka1-2016-qualb.contest.atcoder.…

問題 問題概要 区間に対するクエリの問題。区間全体に対して、値を変更するため、遅延segment treeを使う。 解法 この問題とほぼ同じことをするだけ. mmxsrup.hatenablog.com 変更するのは以下の3点 (1)遅延情報の適用方法 -segは区間におけるAとBの色の数を…

問題 問題概要 区間に対するクエリの問題。区間全体に対して、値を変更するため、遅延segment treeを使う。 解法 さっぱりわからなかった。蟻本に書いてある、segtreeで範囲に対する最小値を求めるRMQは変更する値が1つなので、値を変更するのに(logn)で済む…