204 . 區間操作 改

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

ioicamp ioicamp-2021

Description

為了成為資料結構大師，下列的問題肯定難不倒你： 給你一段長度 $N$ 的序列 $a_1,\ldots,a_N$，請你支援 $Q$ 筆操作。

  • $1\;l\;r\;x$：對於所有 $l\le i\le r$，將 $a_i$ 改成 $\min(a_i,x)$。
  • $2\;l\;r\;x$：對於所有 $l\le i\le r$，將 $a_i$ 加上 $x$。
  • $3\;l\;r$：輸出對於所有 $l\le i\le r$，$a_i$ 的總和。
  • $4\;l\;r$：輸出對於所有 $l\le i\le r$，$a_i$ 的最大值。

Input Format

輸入首行有兩個正整數 $N,Q$，代表序列的長度以及操作次數。

次行 $N$ 個正整數 $a_1, a_2,\ldots,a_N$。

接下來 $Q$ 行，每行前三個數字為 $k,l,r$，代表操作的種類以及詢問的區間，若 $k\in \lbrace 1,2\rbrace$，緊接著一個正整數 $x$，代表操作的參數。

所有相鄰數字以單一空格隔開。

  • $1\le N,Q\le 2\times 10^ 5$
  • $1\le a_i, x\le 10^ 7$
  • $1\le k\le 4$
  • $1\le l\le r\le N$

Output Format

對於所有輸出操作，輸出指定的值。

Sample Input 1

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

Sample Output 1

16
8
15
8
35
10

Hints

Problem Source

IOICamp 2021 Day2 pD

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~20 無額外限制 100

Testdata and Limits

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