833 . 寶石研究

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

66.7% (4/6)

Tags

apcsc apcsc-exam1

Description

今天，小 Y 與小 P 來到了 APCS 國。在這個國家中，總共有 $N$ 個城鎮（城鎮以 $1$ 到 $N$ 編號），每個城鎮都有恰好一個寶石，而每個寶石都可以用一個數字，代表他們的美麗程度。第 $i$ 個城鎮的寶石的美麗程度，他們以 $a_i$ 來表示。

接下來，小 Y 與小 P 會對這些城鎮做一些研究，內容分別如下：

  1. 增加美麗度：小 Y 與小 P 會選擇兩個數字 $x, y$，並且把城鎮 $x, x + 1, \dots, y - 1, y$ 的寶石的美麗程度都加上一個正整數 $z$。
  2. 寶石反轉：小 Y 與小 P 會選擇兩個數字 $x, y$，並且對調城鎮 $x$ 與城鎮 $y$ 的寶石、城鎮 $x + 1$ 與城鎮 $y - 1$ 的寶石、$\dots$，以此類推。
  3. 詢問：小 Y 與小 P 會選擇兩個數字 $x, y$，他們會問城鎮 $x, x + 1, \dots, y$ 的寶石中，美麗程度的最大值是多少。

上面那些研究中，他們會按照順序執行 $Q$ 個研究，並且至少包含一個詢問研究。

現在，給你這些資訊，針對每個詢問研究，請你輸出相對應的答案。

Input Format

輸入的第一行包含兩個正整數 $N, Q(1 \leq N, Q \leq 1000)$，分別代表 APCS 國的城鎮數量，以及進行的研究數量。

接下來的一行，包含 $N$ 個正整數 $a_1, a_2, \dots, a_N(1 \leq a_i \leq 1000)$，$a_i$ 代表第 $i$ 個城鎮的寶石的美麗程度。

接下來的 $Q$ 行，第 $i$ 行代表第 $i$ 個研究的內容。第 $i$ 行的第一個正整數為 $t_i$，代表第 $i$ 個研究的種類。

  • 如果 $t_i = 1$，代表這是一個增加美麗度的研究。接下來會有三個正整數 $x_i, y_i, z_i$，代表小 Y 與小 P 想要把城鎮 $x_i, x_i + 1, \dots, y_i$ 的寶石的美麗程度增加 $z_i$。
  • 如果 $t_i = 2$，代表這是一個寶石反轉的研究。接下來會有兩個正整數 $x_i, y_i$，代表小 Y 與小 P 想要對調城鎮 $x_i$ 與城鎮 $y_i$ 的寶石、城鎮 $x_i + 1$ 與城鎮 $y_i - 1$ 的寶石，$\dots$，以此類推。
  • 如果 $t_i = 3$，代表這是一個詢問的研究。接下來會有兩個正整數 $x_i, y_i$，代表小 Y 與小 P 想要知道城鎮 $x_i, x_i + 1, \dots, y_i - 1, y_i$ 中，寶石裡面最大的美麗程度的值是多少。

題目保證 $1 \leq t_i \leq 3, 1 \leq x_i \leq y_i \leq N, 1 \leq z_i \leq 1000$。

Output Format

對於每個詢問的研究，請輸出一個數字於一行，代表那個詢問研究的答案。

Sample Input 1

4 4
3 1 4 2
3 1 1
3 2 2
3 3 3
3 4 4

Sample Output 1

3
1
4
2

Sample Input 2

5 3
3 1 4 1 5
3 3 4
1 4 5 10
3 3 4

Sample Output 2

4
11

Sample Input 3

5 8
2 4 3 5 6
3 1 2
2 2 3
3 1 2
2 2 4
3 1 2
1 1 1 8
3 1 5
3 2 5

Sample Output 3

4
3
5
10
6

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 3~8 只有詢問的研究，並且保證 $x_i = y_i$ 10
3 3~14 不會有寶石反轉的研究 30
4 0~24 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 4
1 1000 524288 65536 1 4
2 1000 524288 65536 1 4
3 1000 524288 65536 2 3 4
4 1000 524288 65536 2 3 4
5 1000 524288 65536 2 3 4
6 1000 524288 65536 2 3 4
7 1000 524288 65536 2 3 4
8 1000 524288 65536 2 3 4
9 1000 524288 65536 3 4
10 1000 524288 65536 3 4
11 1000 524288 65536 3 4
12 1000 524288 65536 3 4
13 1000 524288 65536 3 4
14 1000 524288 65536 3 4
15 1000 524288 65536 4
16 1000 524288 65536 4
17 1000 524288 65536 4
18 1000 524288 65536 4
19 1000 524288 65536 4
20 1000 524288 65536 4
21 1000 524288 65536 4
22 1000 524288 65536 4
23 1000 524288 65536 4
24 1000 524288 65536 4
Submit
Back to Top