algoNote

プログラミング関連

セグメントツリーを勉強した

セグメントツリーを勉強したのでメモとしてコードを載せておきます。

区間add - 区間sum

RSQ and RAQ | Aizu Online Judge

列に対して次の2種類のクエリを処理します。

  1. 区間[l,r]に値xを一様に加える
  2. 区間[l,r]の値の和を求める

lazy[v] := 頂点vの区間に足されている値 とするセグメントツリーを作ります。

区間update - 区間min

RMQ and RUQ | Aizu Online Judge

列に対して次の2種類のクエリを処理します。

  1. 区間[l,r]のすべての値をxに更新する
  2. 区間[l,r]の値の最小値を求める

lazy[v] := 頂点vの区間をすべて上書きする値 とするセグメントツリーを作ります。

区間add - 区間max

  1. 区間[l,r]のすべての値にxを加える
  2. 区間[l,r]の値の最大(最小)値を求める

これらのクエリを処理するセグメントツリーをStarry Sky Treeと呼ぶらしいです。実装は上の2つを組み合わせるだけです。

code-festival-2015-final-open.contest.atcoder.jp

押すボタンを決めたら、誰が押すかは関係が無いので、押している区間が最大でいくつ被っているかがわかればいいです。

N-1点以上取るために必要な人数の最小値が欲しいので、どれか1つ押さない場合について考えます。

はじめにすべて押すと仮定してStarrySkyTreeですべての区間に+1しておいて、押さないボタンを決めたらその区間を-1して最大を計算、を繰り返します。

Codeforces Round #149 Div2 E.XOR on Segment

codeforces.com

与えられる数列a[i]に対して次の2種類のクエリを処理します。

  1. 区間[l,r]のすべての値にxをXORする
  2. 区間[l,r]の値の和を求める

「ある区間の値すべてにXORをした結果の和」は簡単には求まらないので区間add区間sumのようにはいきません。

そこで、値をビットに分割してそれぞれ1ビット目のセグメントツリー、2ビット目のセグメントツリー...というようにビット毎にセグメントツリーを作ります。

kビット目のセグメントツリーは、{a[0]のkビット目, a[1]のkビット目, a[2]のkビット目 ... }という列を元に構成して、各頂点が対応する区間の要素の和を持つようにします(val[i])。

XORのクエリについては、xのkビット目を見て1ならk番目のセグメントツリーに対して区間[l,r]の値を反転させます。ここで lazy[v] := 頂点vの区間の値を反転させるかどうか として遅延伝搬で処理します。頂点vの区間のビットを反転すると val[v] = 区間の幅 - val[v] となります。