問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 70
作問者 : shimomireshimomire
3 ProblemId : 383 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:48:15

問題文

長さ N の区間 [0,N) の釣り堀で魚釣りをします。

全ての魚は以下の規則に従って動きます。

  • 時刻 t で左向きで位置 x にいる魚は時刻 t+1 で、位置 x1 に向きを変えずに移動する。
    ただし、x=0 の魚(位置 x1 に移動出来ない魚)は、そのままの位置で右向きに向きを変える。
  • 同様に、時刻 t で右向きで位置 x にいる魚は時刻 t+1 で、位置 x+1 に向きを変えずに移動する。
    ただし、x=N1 の魚(位置 x+1 に移動出来ない魚)は、そのままの位置で左向きに向きを変える。
(つまり、魚から見て正面に移動できれば 1 進み、移動できなければそのまま反転する。)

はじめ t=0 では、釣り堀に魚は存在しません。
各時刻 t (1tQ) において、以下の 3 種類のいずれかのクエリが与えられるので Q コのクエリを順番に処理してください。
t 番目のクエリ(1-indexed)は、時刻 t で実行されます。
  1. 'L y z' ー 位置 yz 匹の魚が左向きに放たれる。( z 匹の魚は全て左を向く)
  2. 'R y z' ー 位置 yz 匹の魚が右向きに放たれる。( z 匹の魚は全て右を向く)
  3. 'C y z' ー 時刻 t で区間 [y,z) 内にいる魚の総数を出力する。

入力

N Q
x1 y1 z1

xi yi zi

xQ yQ zQ

1 行目には、区間の長さを表す整数 N (2N2×104)とクエリの数を表す整数 Q (1Q2×104) が与えられる。
2 行目から Q 行、問題文中のクエリのいずれかの形式で与えられる。
xi,yi,ziの制約は以下の通り

  • xi=L または xi=R の時、0yi<N かつ 1zi108
  • xi=C の時、0yi<ziN

出力

xi=C のクエリに対して、与えられた順番に答えを出力してください。
出力毎に改行してください。

サンプル

サンプル1
入力
10 3
R 2 1
L 5 1
C 4 5
出力
2

各時刻での魚の動きは以下の通り(Lは左向きの魚,Rは右向きの魚,{...}はその位置の魚のリスト,-はその位置に魚がいないことを表す。)
t=0
----------
t=1
--{R}-------
t=2
---{R}-{L}----
t=3
----{R,L}-----

サンプル2
入力
5 5
L 1 2
R 4 2
C 2 4
C 2 4
C 2 4
出力
0
2
4

各時刻での魚の動きは以下の通り
t=0
-----
t=1
-{L,L}---
t=2
{L,L}---{R,R}
t=3
{R,R}---{L,L}
t=4
-{R,R}-{L,L}-
t=5
--{R,R,L,L}--

境界まで移動すると魚は反転します
サンプル3
入力
4 3
R 3 3
C 0 4
C 1 2
出力
3
0

各時刻での魚の動きは以下の通り
t=0
----
t=1
---{R,R,R}
t=2
---{L,L,L}
t=3
--{L,L,L}-

サンプル4
入力
10 10
C 3 8
L 1 2
R 7 3
C 1 5
C 0 6
L 2 3
R 3 5
C 2 10
R 7 1
L 6 1
出力
0
0
2
10

サンプル5
入力
20 20
R 5 3
L 11 4
R 18 1
R 10 1
R 16 2
R 12 4
C 4 5
C 2 16
L 14 5
C 3 19
C 3 9
R 8 5
C 15 16
C 1 2
L 10 2
L 11 4
L 0 3
R 18 2
C 6 13
C 8 10
出力
0
12
20
0
2
0
8
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。