読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Educational Codeforces Round 6 E. New Year Tree

Codeforces 遅延セグメント木 Euler Tour

問題

codeforces.com

問題概要

木が与えられ、各頂点は色 ci で塗られている。 以下の 2 種類のクエリを処理する。

  • 木を根とする部分木に属する全ての頂点の色を c に塗り替える
  • 木を根とする部分木に属する頂点の色の種類数を出力する

解法

各頂点に pre-order で番号をつける。このようにすると部分木と区間を対応付けられる。

頂点 1 の部分木を色 c で塗りつぶすことは、区間 [1,6] を c で塗りつぶすことに対応する。

f:id:pekempey:20160122150511p:plain

これで区間の問題に変わった。やりたいことは

  • 区間を x で塗りつぶす
  • 区間の色の種類数を求める

の 2 つである。色の種類数が厄介に見えるが、今回は 60 種類しか色がないため色の集合をビットで表して OR すれば求まる。

区間塗りつぶしと区間 OR はどちらも遅延セグ木で対応可能。

Educational Codeforces Round 6 E. New Year Tree

Educational の E は毎回苦戦してたけど今回は解けた。