15061506 SUSTech Online Judge
Problem 1506 --Irotas's Robot

1506: Irotas's Robot

Time Limit: 3 Sec  Memory Limit: 512 MB
Submit: 288  Solved: 51
[Submit][Status][Web Board]

Description

A robot resides in a linear field, where positions are from left to right labelled as \(0, 1, 2, \dots, C-1, C\).

The robot may accept an integer \(k\) as command. Suppose the robot is at position \(x\). Its reponse will be moving \(k\) units rightwards as long as it stays within \([0, C]\). Note that \(k\) may be negative, meaning that the robot will move \(|k|\) units leftwards. The final position is described as \(x' = \max(0, \min(C, x + k))\).

The central computer stores an operation sequence \(\{y_1, y_2, \dots, y_N\}\), on which the robot will execute sequentially. Irotas, the researcher, may also insert a new command to the sequence, or remove a command from it. Meanwhile, you need to answer Irotas's question every time she asked so: where will the robot eventually be if she initially places the robot at \(x_0\)?

Formally speaking, let \(N\) denote the length of the operation sequence at any time. You are asked to support the following actions:

  1. Irotas inserted a new command \(y_{new}\) into the operation sequence, right before \(y_k\) (\(k \in [1, N + 1]\)). If \(k=N+1\), the command is inserted at the end of the sequence.
  2. Irotas removed \(y_k\) from the operation sequence (\(k \in [1, N]\)).
  3. Irotas gives you \(x_0\) as the initial position and queries the eventual position.

Input

The first line contains two integers \(C, N\).

The second line contains \(N\) integers, representing \(y_1, y_2, \dots, y_N\).

The third line contains an integer \(M\), denoting the number of actions to perform.

For the following \(M\) lines, each line is in one of the three formats, denoting the three actions respectively:

  1. \(\text{ins}\ k\ y_{new}\)
  2. \(\text{rem}\ k\)
  3. \(\text{ask}\ x_0\)

输入限制

\(C, x_0 \in [0, 10^9]\)

For the operation sequence \(\{y_1, y_2, \dots, y_N\}\), at any time we have:

  • \(0 \le N \le 2 \times 10^5\) (i.e. "remove" operation will not occur when \(N = 0\), "insert" operation will not occur when \(N = 2 \times 10^5\))
  • \(|y_i| \le 10^9\)
  • \(0 \le M \le 10^5\)

Output

For each action 3, output one line containing a single number, representing the final result.

Sample Input

10 3
4 -5 2
5
ask 7
rem 1
ask 7
ins 2 -3
ask 7

Sample Output

7
4
2

HINT

不要使用任何与堆和BST相关的STL!

Source

 

[Submit][Status]