ABC170 E - Smart Infants (500)
最初の考察
それぞれの園児について値といる幼稚園を持っておく
それぞれの幼稚園にいる園児を優先度付きキューで持っておく
一回移動する毎にそれぞれの優先度付きキューの最大値を取得してその中での最小値を出力する
キューの最大値を確認してその園児のいる幼稚園が別の所だった場合はキューから捨てて次を見る
一回のクエリ毎に最小値を求めるのは$ O(Q)だが定数倍が$ 2 \times 10^5と非常に大きいのでTLE
最終的な考察
毎回最小値を求めるのは遅いのでセグ木で最小値を持っておき、クエリ毎に一部を更新する
定数部分が$ 2 \times 10^5から$ \log (2 \times 10^5)になるので間に合う