No.259 セグメントフィッシング+

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 27
作問者 : shimomireshimomire
2 ProblemId : 396 / 出題時の順位表

問題文

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

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

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

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

入力

$N$ $Q$
$x_1$ $t_1$ $y_1$ $z_1$
$\cdots$
$x_i$ $t_i$ $y_i$ $z_i$
$\cdots$
$x_Q$ $t_Q$ $y_Q$ $z_Q$

1 行目には、区間の長さを表す整数 $N$ ($2 \le N \le 2 \times 10^5$)とクエリの数を表す整数 $Q$ ($1 \le Q \le 8*10^4$) が与えられる。
2 行目から $Q$ 行、問題文中のクエリのいずれかの形式で与えられる。
$t_i$,$x_i$,$y_i$,$z_i$の制約は以下の通り

  • $0 \le t_1 < \cdots < t_i < \cdots < t_Q \le 10^8$
  • $x_i = L$ または $x_i = R$ の時、$0 \le y_i < N$ かつ $1 \le z_i \le 10^8$。
  • $x_i = C$ の時、$0 \le y_i < z_i \le N$。

出力

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

サンプル

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

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

サンプル2
入力
5 4
L 1 1 2
R 2 4 2
C 3 2 4
C 5 2 4
出力
0
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
入力
10 10
C 1 3 8
L 2 1 2
R 3 7 3
C 4 1 5
C 5 0 6
L 6 2 3
R 7 3 5
C 8 2 10
R 9 7 1
L 10 6 1
出力
0
0
2
10

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。