TopCoder

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

66.7% (4/6)

Tags

Description

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

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

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

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

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

Input Format

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

接下來的一行,包含 N 個正整數 a1,a2,,aN(1ai1000)ai 代表第 i 個城鎮的寶石的美麗程度。

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

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

題目保證 1ti3,1xiyiN,1zi1000

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 只有詢問的研究,並且保證 xi=yi 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