yukicoder No.619 CardShuffle

この記事は yukicoder No.619 CardShuffle の解説です。

考え方

問題を見ればセグ木を使えば解けることは予想できる。

セグ木に載せるべき「部分的な計算結果」どうしをつなげて掛け算をしたときの掛け算の影響範囲を考えると、「部分的な計算結果」は a+b+c の形をしていると都合がよいことが分かる。

セグ木の各ノードに a+b+c の形をした式の「 a, b, c の値」と「 + または * の演算子」を載せる。

数字カードはセグ木の葉ノードに対応し、演算子カードは葉でないノードに対応する。

数字カードは a+b+c の形にならず、値を 1 つだけもつ。また、値を 1 つだけもつものどうしを * でつないだ場合も値を 1 つだけもつ。

値を 1 つだけもつ場合は x-x+x のようにしておくと都合がよい。a+b+c の形になる場合は b は負になり得ないので、b が負であるならば値を 1 つだけもっていると判定できる。0-0+0 の場合は b が負にならないが、辻褄は合う。

a+b+c と d+e+f の掛け算については 4 通り考える必要があり、

• b≧0 かつ e≧0 のとき a+(b+cd+e)+f
• b≧0 かつ e<0 のとき a+(b)+cd
• b<0 かつ e≧0 のとき cd+(e)+f
• b<0 かつ e<0 のとき cd+(-cd)+cd

のようになる。一方、足し算については x-x+x のようにしておいたことにより場合分けが不要になり、

• a+(b+c+d+e)+f

のようになる。

交換クエリにおいて、演算子カードの交換が発生し得るので、「カード列のインデックス→セグ木のインデックス」の変換ができると楽。

交換後の再計算の際に、値の入っていないノードとの計算をする場合がある。その場合は 0 との足し算をするようにすると楽。

入力の読み込み方

セグ木上を通りがけ順で移動しながらその場所に入力の値を載せていく。

入力を読み込む毎にインデックス変換用の配列にインデックスを入れる。

前処理としての計算も入力を読み込むついでにやってしまう（左側で再帰、真ん中で演算子を読み込む、右側で再帰、左右の計算結果どうしで演算、の順でやる）。

カード列のインデックス
               8
       4              12
   2       6      10      14
 1   3   5   7   9  11  13  15

 
セグ木のインデックス
               1
       2               3
   4       5       6       7
 8   9  10  11  12  13  14  15

交換クエリ

数字カードの交換の場合は交換したカードの親ノードから根に向かって再計算する。

演算子カードの交換の場合はそのノードから根に向かって再計算する。

質問クエリ

計算範囲の左端と右端から同時に根に向かって親ノードが一致するまで演算していき、それぞれの計算結果どうしで演算する。

実装例

#226631 一応この記事を書いている段階では最速らしい。