908 . 月球運算

Submit out of contest
Status
Discussion / Solution
Back to Problems List

Description

在月球上，加法規則與地球不同，被稱之為 月球加法。對於兩個個位數 $a$ 和 $b$ 的月球加法定義如下：

月球加法 ($\oplus$)： $a \oplus b = \max(a,b)$

將其推廣到兩個任意位數的數字 $x$ 和 $y$ ：

月球加法 ($\oplus$)：取 $x$ 和 $y$ 的每一位，逐位比較，選取較大部位組成新數。例如：

$$ 123 \oplus 456 = 456 $$

$$ 321 \oplus 213 = 323 $$

現在給定一個長度為 $n$ 的數列 $a[1..n]$，需要支持以下操作：

  1. 區間查詢：給定 $l,r$ 對區間 $[l, r]$ 計算月球加法的結果
  2. 區間加法：給定 $l,r$ 和 $v$ ，將區間 $[l, r]$ 內所有數用月球加法加上 $v$
  3. 區間更新：給定 $l,r$ 和 $v$ ，將區間 $[l, r]$ 內所有數設成 $v$

Input Format

輸入有三行

第一行包含兩個正整數 $n$ 和 $q$，分別表示數組長度和操作數量。

第二行包含 $n$ 個正整數，表示數組 $a[1..n]$ 的初始值。

接下來 $q$ 行，每行描述一個操作，分為以下四種形式：

  • $1\ l\ r$：輸出對區間 $[l, r]$ 計算月球加法的結果
  • $2\ l\ r\ v$：將區間 $[l, r]$ 的所有值加上 $v$
  • $3\ l\ r\ v$：將區間 $[l, r]$ 的所有值設置為 $v$
  • $1 \leq n, q \leq 10^ 5$
  • $1 \leq a[i], x < 10^ 9$
  • $1 \leq l \leq r \leq n$
  • $1 \leq v < 10^ 9$

Output Format

對於每一個 type 1 詢問，回答一個正整數代表答案

Sample Input 1

5 4
2 5 6 18 9
1 2 2
2 3 3 8
3 1 1 12
1 1 4

Sample Output 1

5
18

Sample Input 2

8 10
871026982 686999126 222809490 328782598 546250569 999606744 230235754 602991855
3 4 8 317382166
1 1 2
2 1 5 918448866
1 4 7
2 1 7 237130621
3 6 6 51489530
2 6 6 688021820
1 3 5
2 1 4 60153526
3 2 7 467902754

Sample Output 2

886999986
918488866
938889896

Hints

這個運算有結合律嗎？有交換律嗎？

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~13 $ n,q \leq 3000$ 20
3 14~25 對第 2 和第 3 個操作 $l=r$ 20
4 0~37 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2 4
1 1000 262144 65536 1 2 4
2 1000 262144 65536 2 4
3 1000 262144 65536 2 4
4 1000 262144 65536 2 4
5 1000 262144 65536 2 4
6 1000 262144 65536 2 4
7 1000 262144 65536 2 4
8 1000 262144 65536 2 4
9 1000 262144 65536 2 4
10 1000 262144 65536 2 4
11 1000 262144 65536 2 4
12 1000 262144 65536 2 4
13 1000 262144 65536 2 4
14 1000 262144 65536 3 4
15 1000 262144 65536 3 4
16 1000 262144 65536 3 4
17 1000 262144 65536 3 4
18 1000 262144 65536 3 4
19 1000 262144 65536 3 4
20 1000 262144 65536 3 4
21 1000 262144 65536 3 4
22 1000 262144 65536 3 4
23 1000 262144 65536 3 4
24 1000 262144 65536 3 4
25 1000 262144 65536 3 4
26 1000 262144 65536 4
27 1000 262144 65536 4
28 1000 262144 65536 4
29 1000 262144 65536 4
30 1000 262144 65536 4
31 1000 262144 65536 4
32 1000 262144 65536 4
33 1000 262144 65536 4
34 1000 262144 65536 4
35 1000 262144 65536 4
36 1000 262144 65536 4
37 1000 262144 65536 4
Submit out of contest
Back to Top