QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 2048 MB Total points: 100

#785. Historical Maximum Value

Statistics

Given a sequence $A_1, A_2, \cdots, A_n$ with the length $n$. You need to process the following $m$ queries:

  • 1 l r x: For each $l \leq i \leq r$, let $A_i \leftarrow A_i + x$.
  • 2 l r x: For each $l \leq i \leq r$, let $A_i \leftarrow x$.
  • 3 l r: Print the maximum value of $A_i$ when $l \leq i \leq r$.
  • 4 l r: Print the historical maximum value of $A_i$ when $l \leq i \leq r$.

Input

The first line of the input contains two integers $n$ and $m$ - the length of the sequence and the number of the operations.

The next line of the input contains $n$ integers $A_1, A_2, \cdots, A_n$, describes the sequence $A$ at the initial time.

The next $m$ lines of the input describe one query per line.

Output

For each query of type 3 or 4, you need to output a line with a single integer indicating the answer.

Samples

Input 1

5 10
-5 6 -10 3 8 
4 3 5
4 2 4
1 4 4 -7
1 3 3 1
4 1 1
1 2 4 7
1 1 4 9
2 1 3 9
3 1 1
4 4 5

Output 1

8
6
-5
9
12

Input 2

6 12
-5 4 -3 0 9 6
3 1 5
2 2 4 2
1 1 3 5
1 3 5 -4
2 4 5 1
4 1 6
1 3 6 2
4 1 2
3 5 6
1 1 6 -1000000000
3 2 4
4 2 4

Output 2

9
9
7
8
-999999993
7

Input 3

20 30
-300641398 643562768 -973662722 -828209263 -309447205 -598693447 -101747247 -218359912 223156787 144550482 -764855619 527931534 652711445 -378234863 -861768168 -746317163 954632121 -742544956 -683774548 206177971 
1 10 17 -978752351
3 6 20
2 12 19 -52976069
2 14 18 -820873406
2 5 13 -809636884
2 1 15 -92483004
1 3 5 697386996
1 9 14 -199066725
2 1 6 -420516547
4 1 14
1 17 19 754289671
4 8 12
1 9 12 771518399
2 7 13 -343914441
3 3 19
2 9 13 360029137
3 1 12
2 2 8 616334876
2 15 15 -469894325
1 6 9 -721353073
1 3 5 335823776
1 4 6 -811222500
4 7 11
1 2 5 -621714033
2 5 16 165108179
2 16 19 -650336428
4 9 11
1 11 14 644010439
4 6 13
4 4 12

Output 3

223156787
652711445
527931534
701313602
360029137
616334876
479968670
809118618
952158652

Scoring

It is guaranteed that $1 \leq n,m \leq 5 \times 10^5, -10^9 \leq A_i \leq 10^9, 1 \leq l \leq r \leq n, -10^9 \leq x \leq 10^9$.

  • Subtask 1(10 points): $1 \leq n,m \leq 5000$
  • Subtask 2(20 points): there's no query of type 1.
  • Subtask 3(20 points): there's no query of type 2.
  • Subtask 4(50 ponits): no additional constraints.

给定一个长度为 $n$ 的序列 $A_1, A_2, \cdots, A_n$,你需要进行 $m$ 次以下操作:

  • 1 l r x: 对每个 $l \leq i \leq r$,令 $A_i \leftarrow A_i + x$。
  • 2 l r x:对每个 $1 \leq i \leq r$,令 $A_i \leftarrow x$。
  • 3 l r:询问满足 $l \leq i \leq r$ 的 $A_i$ 的最大值。
  • 4 l r:询问满足 $l \leq i \leq r$ 的 $A_i$ 的历史最大值。

输入格式

输入的第一行包含两个整数 $n, m$,表示序列的长度与操作次数。

接下来一行,包含 $n$ 个整数 $A_1, A_2, \cdots, A_n$,表示初始时序列 $A$ 的值。

接下来 $m$ 行,每行包含若干个整数,描述一个操作。

输出格式

对于所有询问操作,输出一行一个整数,表示答案。

样例数据

样例 1 输入

5 10
-5 6 -10 3 8 
4 3 5
4 2 4
1 4 4 -7
1 3 3 1
4 1 1
1 2 4 7
1 1 4 9
2 1 3 9
3 1 1
4 4 5

样例 1 输出

8
6
-5
9
12

样例 2 输入

6 12
-5 4 -3 0 9 6
3 1 5
2 2 4 2
1 1 3 5
1 3 5 -4
2 4 5 1
4 1 6
1 3 6 2
4 1 2
3 5 6
1 1 6 -1000000000
3 2 4
4 2 4

样例 2 输出

9
9
7
8
-999999993
7

样例 3 输入

20 30
-300641398 643562768 -973662722 -828209263 -309447205 -598693447 -101747247 -218359912 223156787 144550482 -764855619 527931534 652711445 -378234863 -861768168 -746317163 954632121 -742544956 -683774548 206177971 
1 10 17 -978752351
3 6 20
2 12 19 -52976069
2 14 18 -820873406
2 5 13 -809636884
2 1 15 -92483004
1 3 5 697386996
1 9 14 -199066725
2 1 6 -420516547
4 1 14
1 17 19 754289671
4 8 12
1 9 12 771518399
2 7 13 -343914441
3 3 19
2 9 13 360029137
3 1 12
2 2 8 616334876
2 15 15 -469894325
1 6 9 -721353073
1 3 5 335823776
1 4 6 -811222500
4 7 11
1 2 5 -621714033
2 5 16 165108179
2 16 19 -650336428
4 9 11
1 11 14 644010439
4 6 13
4 4 12

样例 3 输出

223156787
652711445
527931534
701313602
360029137
616334876
479968670
809118618
952158652

子任务

对于所有数据,$1 \leq n,m \leq 5 \times 10^5, -10^9 \leq A_i \leq 10^9, 1 \leq l \leq r \leq n, -10^9 \leq x \leq 10^9$。

  • Subtask 1(10 points): $1 \leq n,m \leq 5000$
  • Subtask 2(20 points): 不存在操作 $1$。
  • Subtask 3(20 points): 不存在操作 $2$。
  • Subtask 4(50 ponits): 没有额外的限制。