yukicoder No.151 セグメントフィッシング

問題

No.151 セグメントフィッシング - yukicoder

左右の長さ$N$の釣堀がある。
釣堀内の魚は、左右の端につくまで速度１で動いていて、端では時間１かけて方向転換する。
最初釣堀には魚はいない。
時間$Q$まで時間１毎に以下のクエリが与えられるので順次処理する。

1. 釣堀内の位置$y$に$z$匹の魚を右向きに放す
2. 釣堀内の位置$y$に$z$匹の魚を左向きに放す
3. 釣堀内の位置$[y,z)$にいる魚の数を求める

出力は、クエリ３毎に求めた魚の数。

解法

単純に考えると、釣堀内の各位置にいる魚の数と向きを記憶しておき、時間$Q$の経過をシミュレーションして魚の位置を時間ごとに移動させ、クエリ３が来たら指定位置の魚の数の和を計算することで$O(Q*N)$となる。

• 処理ごとのオーダー
  • シミュレーション（魚の移動）$O(N)$
  • 魚の追加 $O(1)$
  • 魚の数を数える $O(N)$
• 全体で $O(Q*N)$

$Q,N \le 2*10^4$ なので、$O(Q*N) = O(4*10^8)$となり、C++ならこれを実装すれば通るようだ。

Rubyの場合はこれだと厳しいので、２つのポイントで効率化する。

• 時間経過をシミュレーション・・・毎時間魚の位置を移動させるのではなく、時間ごとに参照するインデックスをずらせばよい
• 指定位置の魚の数の和を求める・・・問題名にある通りセグメントツリー（BITでよい）で数を保持して和を求める

これにより、以下のようにオーダーが変わり、全体で$O(Q*\log(N))$とできる。

• 処理ごとのオーダー
  • シミュレーション（魚の移動）$O(1)$（処理不要）
  • 魚の追加 $O(\log(N))$
  • 魚の数を数える $O(\log(N))$
• 全体で $O(Q*\log(N))$

図解

魚は以下のように釣堀の中を一周すると考えると、保持するデータ構造は配列1本で行ける。
時間１経過すると、魚は配列上右に１進む。末尾の魚は先頭に来る。

これを、解法のポイント１のように、時間とともに魚が進むのではなくインデックスがずれると考えると、魚の移動処理がいらず以下のようになる。

そしてこの配列の要素をBITで管理すれば、$(z-1$までの$sum)-(y-1$までの$sum)$で区間の和が$O(\log(N))$で計算できる。
インデックスをずらす考え方の場合、以下のように端をまたぐ区間の合計を求めることになり得るので注意して実装する。

#12946 No.151 セグメントフィッシング - yukicoder
※記事書いてからコード見直したら、上記解説とは逆に魚が配列を左に進む想定にしてた。

N,Q=gets.split.map(&:to_i)
NN=N*2
BIT=[0]*(NN+1)
def add x,v;(BIT[x]+=v;x+=x&-x)while BIT[x];end
def sum x;s=0;(s+=BIT[x];x&=x-1)while x>0;s;end
Q.times{|t|
  x,*v=gets.split
  y,z=v.map(&:to_i)
  case x
  when ?L
    add (y+t)%NN+1,z
  when ?R
    add (-y-1+t)%NN+1,z
  when ?C
    ty,tz=(y+t)%NN,(z-1+t)%NN
    uz,uy=(-z+t)%NN,(-y-1+t)%NN
    p sum(tz+1)-sum(ty)+(ty<=tz ?0:sum(NN))+
      sum(uy+1)-sum(uz)+(uz<=uy ?0:sum(NN))
  end
}