M - Adjusting Building Heights Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

高橋君は、一列に並ぶビル群の設計を行っています。最初、列は空です。

これから Q 個の操作が順に行われます。操作には次の 3 種類があります。

  • 操作 1：高さ x の新しいビルを、列の右端に追加する。
  • 操作 2：列の右端のビルを取り除く。この操作は、列が空でないときにのみ与えられる。
  • 操作 3：現在の列について、以下で定義される値を求める。

操作 3 では、その時点で列に並んでいるビルの個数を M とし、左から i 番目のビルの高さを C_i とします。

高橋君は、各ビルの高さを変えずに維持するか、低くすることができます。具体的には、各ビル i について調整後の高さ B_i を、0 \leq B_i \leq C_i を満たす整数として自由に選べます。このとき、隣り合うビルの調整後の高さの差の絶対値が定数 D 以下、すなわちすべての 1 \leq i < M について

|B_i - B_{i+1}| \leq D

を満たすようにしたいです。

B_i = 0（1 \leq i \leq M）とすれば条件は必ず満たされるので、条件を満たす選び方は常に存在します。そのような選び方のうち、合計

B_1 + B_2 + \cdots + B_M

としてあり得る最大値を求めてください。ただし、M = 0（列が空）のときの答えは 0 とします。

なお、操作 3 では答えを計算するだけで、列に並んでいるビルの高さは変化しません。

制約

  • 1 \leq Q \leq 10^5
  • 0 \leq D \leq 10^9
  • 操作 1 で与えられる x は 0 \leq x \leq 10^9 を満たす
  • 操作 2 は列が空でないときにのみ与えられる
  • 入力はすべて整数である

入力

Q D
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

1 行目には、操作の個数 Q と、隣り合うビルの調整後の高さの差の絶対値の上限 D が、スペース区切りで与えられます。

続く Q 行には、操作が時系列順に与えられます。各操作は次のいずれかの形式です。

  • 1 x ：高さ x のビルを列の右端に追加する。
  • 2 ：列の右端のビルを取り除く。
  • 3 ：現在の列について質問する。

出力

操作 3 が与えられるたびに、その質問への答えを 1 行に整数で出力してください。

入力例 1

10 2
3
1 5
3
1 1
3
1 10
3
2
3
2

出力例 1

0
5
4
7
4

入力例 2

9 0
1 3
1 1
3
2
1 3
3
1 0
3
2

出力例 2

2
6
0

入力例 3

22 3
1 8
1 2
1 9
3
1 4
3
2
1 15
1 6
3
2
2
3
1 0
1 12
3
2
1 7
1 7
3
2
3

出力例 3

12
16
26
12
13
19
13

入力例 4

50 5
1 100
1 1
1 20
3
1 35
1 0
3
2
1 60
3
1 55
1 5
3
2
2
3
1 1000000000
3
1 999999990
1 10
3
2
3
2
2
3
1 42
1 17
1 88
1 23
3
2
1 77
3
1 0
1 100
3
2
2
2
3
1 15
1 30
1 45
3
2
2
3
2
3

出力例 4

13
18
40
54
40
61
85
87
40
123
127
95
100
158
113
100

入力例 5

12 1000000000
3
1 1000000000
3
1 0
3
1 1000000000
3
2
3
2
2
3

出力例 5

0
1000000000
1000000000
2000000000
1000000000
0

Score : 500 pts

Problem Statement

Takahashi is designing a row of buildings. Initially, the row is empty.

There are Q operations performed in order. There are 3 types of operations:

  • Operation 1: Add a new building of height x to the right end of the row.
  • Operation 2: Remove the building at the right end of the row. This operation is only given when the row is not empty.
  • Operation 3: Calculate the value defined below for the current row.

In Operation 3, let M be the number of buildings currently in the row, and let C_i be the height of the i-th building from the left.

Takahashi can either maintain the height of each building or make it shorter. Specifically, for each building i, he can freely choose the adjusted height B_i as an integer satisfying 0 \leq B_i \leq C_i. He wants to make sure that the absolute difference between the adjusted heights of adjacent buildings is at most a constant D. That is, for all 1 \leq i < M:

|B_i - B_{i+1}| \leq D

Since setting B_i = 0 (1 \leq i \leq M) always satisfies the condition, a valid choice of heights always exists. Find the maximum possible sum of the adjusted heights:

B_1 + B_2 + \cdots + B_M

among all valid choices. If M = 0 (the row is empty), the answer is 0.

Note that Operation 3 only calculates the answer and does not change the actual heights of the buildings in the row.

Constraints

  • 1 \leq Q \leq 10^5
  • 0 \leq D \leq 10^9
  • x given in Operation 1 satisfies 0 \leq x \leq 10^9
  • Operation 2 is only given when the row is not empty
  • All input values are integers

Input

Q D
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

The first line contains Q, the number of operations, and D, the upper bound on the absolute difference between the adjusted heights of adjacent buildings, separated by a space.

The following Q lines describe the operations in chronological order. Each operation is in one of the following formats:

  • 1 x : Add a building of height x to the right end of the row.
  • 2 : Remove the building at the right end of the row.
  • 3 : Query the current row.

Output

Each time Operation 3 is given, print the answer to the query on a single line as an integer.

Sample Input 1

10 2
3
1 5
3
1 1
3
1 10
3
2
3
2

Sample Output 1

0
5
4
7
4

Sample Input 2

9 0
1 3
1 1
3
2
1 3
3
1 0
3
2

Sample Output 2

2
6
0

Sample Input 3

22 3
1 8
1 2
1 9
3
1 4
3
2
1 15
1 6
3
2
2
3
1 0
1 12
3
2
1 7
1 7
3
2
3

Sample Output 3

12
16
26
12
13
19
13

Sample Input 4

50 5
1 100
1 1
1 20
3
1 35
1 0
3
2
1 60
3
1 55
1 5
3
2
2
3
1 1000000000
3
1 999999990
1 10
3
2
3
2
2
3
1 42
1 17
1 88
1 23
3
2
1 77
3
1 0
1 100
3
2
2
2
3
1 15
1 30
1 45
3
2
2
3
2
3

Sample Output 4

13
18
40
54
40
61
85
87
40
123
127
95
100
158
113
100

Sample Input 5

12 1000000000
3
1 1000000000
3
1 0
3
1 1000000000
3
2
3
2
2
3

Sample Output 5

0
1000000000
1000000000
2000000000
1000000000
0