🦔
Deque ABC355 C - Loong Trackingを理解し忘れないようにする
問題概要
1~Nまで数字のついたN個のパーツがあり、パーツ1を頭とする。
パーツの処理値は(i,0)とする。
Q回のクエリを発行し、type1ならCの方向にパーツ1を動かし、パーツ2以降は前のパーツの位置に移動する。
type2ならpのパーツの位置を求める。
ハマった点
全探索O(NM)以外のソリューションを思いつかず。。
解説見た
type1について、パーツを管理する際に先頭にパーツ1移動後の値を追加して末尾を削除する。
そうすると、パーツ1が移動したことを示せる。
同時にパーツ2は移動前のパーツ1に移動していることになるし、パーツ3も移動前のパーツ2になる。(i>=2の時、パーツiは移動前のパーツi-1となる。)
上記の先頭に追加して末尾を削除する操作がdequeを用いるとO(1)で出来るので、全体計算量はO(Q)となる。
提出コード
参考元
公式解説記事
Discussion