問題概要
$H \ $階建てのビルに$ \ N \ $台のロボットが配置されている。
$i \ $台目のロボットは$ \ f_i \ $階に設置されており、同じ階に複数のロボットが配置されていることはない。
ロボットの移動命令が$ \ Q \ $回にわたって与えられる。すべての命令を処理した後の各ロボットの位置を求めよ。
命令は$ \ 3 \ $つの整数$ \ k_i,d_i,r_i \ $からなり、$k_i \ $番目までのロボットが$ \ r_i \ $回以下のような移動を繰り返す。
- $d_i = 1 \ $のとき、現在いる階が$ \ H \ $階でないならば$ \ 1 \ $つ上の階へ移動する。
- $d_i = 0 \ $のとき、現在いる階が$ \ 1 \ $階でないならば$ \ 1 \ $つ下の階へ移動する。
また、同じ階にいる他のロボットが上下の階へ移動をしたとき、自身も共に移動する。
制約
- $1 \leq N \leq 10^5$
- $N \leq H \leq 10^9$
- $1 \leq Q \leq 10^5$
- $1 \leq f_i \leq H$
- $1 \leq k_i \leq N$
- $0 \leq d_i \leq 1$
- $1 \leq r_i \leq H$
解説
この問題の重要な点は複数のロボットが同じように移動するという点です。 これらのロボットを全て処理するのは無駄です。 これはUnionFindTree(DisjointSet)を使うことで1つのグループとして管理できます。
ロボットの移動とそれに伴うグループの併合は、C++の場合std::setを使うと簡単に実装できます。
計算量は$ \ O(( N + Q ) \log N) \ $となります。
