問題一覧 > 通常問題

No.259 Segment Fishing +

レベル : / AI推定難易度 : 1725 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 47
作問者 : shimomire
お気に入りにしたユーザー ProblemId : 396 / 自分の提出
問題文最終更新日: 2026-06-26 06:06:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder 1周年記念 復習コンテスト R2 (順位表) の他の問題:

Problem Statement

You go fishing in a fishing pond that is the interval $[0,N)$ of length $N$.

All fish move according to the following rules.

  • A fish facing left at position $x$ at time $t$ moves to position $x−1$ at time $t+1$ without changing its direction.
    However, a fish at $x = 0$ (a fish that cannot move to position $x−1$) stays at the same position and turns to face right.
  • Similarly, a fish facing right at position $x$ at time $t$ moves to position $x+1$ at time $t+1$ without changing its direction.
    However, a fish at $x = N−1$ (a fish that cannot move to position $x+1$) stays at the same position and turns to face left.
(In other words, a fish advances by $1$ if it can move forward in the direction it is facing; otherwise, it stays in place and reverses direction.)

Initially, at $t = 0$, there are no fish in the pond.
You are given $Q$ queries of the following $3$ types. Process them in order.
  1. 'L t y z' ー At time $t$, $z$ fish are released at position $y$ facing left. (All $z$ fish face left.)
  2. 'R t y z' ー At time $t$, $z$ fish are released at position $y$ facing right. (All $z$ fish face right.)
  3. 'C t y z' ー Output the total number of fish in the interval $[y,z)$ at time $t$.

Input

$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$

The first line contains an integer $N$ ($2 \le N \le 2 \times 10^5$) representing the length of the interval and an integer $Q$ ($1 \le Q \le 8*10^4$) representing the number of queries.
The following $Q$ lines, starting from line 2, each give a query in one of the formats described in the problem statement.
The constraints on $t_i$,$x_i$,$y_i$,$z_i$ are as follows.

  • $0 \le t_1 < \cdots < t_i < \cdots < t_Q \le 10^8$
  • When $x_i = L$ or $x_i = R$, $0 \le y_i < N$ and $1 \le z_i \le 10^8$.
  • When $x_i = C$, $0 \le y_i < z_i \le N$.

Output

For each query with $x_i = C$, output the answer, in the order the queries are given.
Print a newline after each output.

Sample

Sample 1
Input
10 3
R 1 2 1
L 2 5 1
C 3 4 5
Output
2

The movement of the fish at each time is as follows (L denotes a fish facing left, R denotes a fish facing right, {...} denotes the list of fish at that position, and - denotes that there are no fish at that position).
$t = 0$
----------
$t = 1$
--{R}-------
$t = 2$
---{R}-{L}----
$t = 3$
----{R,L}-----

Sample 2
Input
5 4
L 1 1 2
R 2 4 2
C 3 2 4
C 5 2 4
Output
0
4

The movement of the fish at each time is as follows.
$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}--

A fish reverses its direction when it reaches the boundary.
Sample 3
Input
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
Output
0
0
2
10

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