Data Structure Marathon

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Cho \(Q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(u_i\) \(v_i\) \(x_i\): Tăng mỗi phần tử từ vị trí \(u_i\) tới vị trí \(v_i\) lên \(x_i\) đơn vị.
• \(2\) \(u_i\) \(v_i\): Tìm giá trị lớn nhất trong các phần tử từ vị trí \(u_i\) tới vị trí \(v_i\).

Yêu cầu: Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((A_i \leq 10^9)\).
• \(Q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi ba số nguyên dương \(u_i\), \(v_i\) và \(x_i\) \((1 \leq u_i \leq v_i \leq N\), \(1 \leq x_i \leq 10^9)\). Số \(2\) theo sau bởi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \leq u_i \leq v_i \leq N)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra giá trị lớn nhất trong các phần tử từ vị trí \(u\) tới vị trí \(v\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3\), \(Q \leq 10^3\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\), chỉ có các thao tác loại \(2\).
• Subtask \(3\) (\(20\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\), các thao tác \(1\) luôn được thực hiện trước các thao tác \(2\).
• Subtask \(4\) (\(30\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\).

Example

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

9
11

Cho dãy \(a\) gồm \(n\) phần tử là các số nguyên dương \(a_{1}, a_{2}, \ldots, a_{N}\). Cho \(q\) thao tác thực liện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(p\) \(x\): Chèn giá trị \(x\) vào giữa hai vị trí \(p - 1\) và \(p\) trong dãy \(a\) \((1 \leq p \leq t + 1\), với \(t\) là số phần tử hiện có trong dãy \(a\). Nếu \(p = t + 1\), chèn \(x\) vào cuối dãy \(a\).
• \(2\) \(u\) \(v\): Tìm giá trị lớn nhất trong các phần tử từ vị trí \(u\) tới vị trí \(v\) \((1 \leq u \leq v \leq t\), với \(t\) là số phần tử hiện có trong dãy \(a).\)

Yêu cầu: Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(n, q\) \((1 \leq n, q \leq 10^{5})\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{N}\) \((a_{i} \leq 10^{9})\).
• \(q\) dòng tiếp theo, mỗi dòng thể hiện 1 truy vấn thuộc 1 trong 2 loại:/
  • \(1\) \(p\) \(x\) \((1 \leq p \leq n, 1 \leq x \leq 10^{9})\).
  • \(2\) \(u\) và \(v\) \((1 \leq u \leq v \leq n)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra giá trị lớn nhất trong các phần tử từ vị trí \(u\) tới vị trí \(v\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 10^{3}\).
• Subtask \(2\) (\(30\%\) số điểm): các thao tác \(1\) luôn được thực hiện trước các thao tác \(2\).
• Subtask \(3\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

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

3
5

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Cho \(Q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(p_i\) \(x_i\): Tăng phần tử ở vị trí \(p_i\) lên \(x_i\) đơn vị.
• \(2\) \(u_i\) \(v_i\): Tính tổng các phần tử từ vị trí \(u_i\) tới vị trí \(v_i\).

Yêu cầu
Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((A_i \leq 10^9)\).
• \(Q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi hai số nguyên dương \(p_i\) và \(x_i\) \((1 \leq p_i \leq N\), \(1 \leq x_i \leq 10^4)\). Số \(2\) theo sau bởi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \leq u_i \leq v_i \leq N)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra tổng các phần atử từ vị trí \(u\) tới vị trí \(v\) trên một dòng.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 10^3\), \(Q \leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\).

Example

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

32
24

Cho dãy \(a\) gồm \(n\) phần tử là các số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\). Cho \(q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(u_{i}\) \(v_{i}\) \(x_{i}\): Tăng mỗi phần tử từ vị trí \(u_{i}\) tới vị trí \(v_{i}\) lên \(x_{i}\) đơn vị.
• \(2\) \(u_{i}\) \(v_{i}\): Tính tổng các phần tử từ vị trí \(u_{i}\) tới vị trí \(v_{i}\).

Yêu cầu: thực hiện tất cả lần lượt \(q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(n, q\) \((1 \leq n, q \leq 10^{5})\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((a_{i} \leq 10^{9})\).
• \(q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi ba số nguyên dương \(u_{i}\), \(v_{i}\) và \(x_{i}\) \((1 \leq u_{i} \leq v_{i} \leq n, 1 \leq x_{i} \leq 10^{9})\). Số \(2\) theo sau bởi hai số nguyên dương \(u_{i}\) và \(v_{i}\) \((1 \leq u_{i} \leq v_{i} \leq n)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra tổng các phần tử từ vị trí \(u\) tới vị trí \(v\) trên một dòng.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 10^{3}\).
• Subtask \(2\) (\(30\%\) số điểm): mọi thao tác loại \(1\) có \(u = v\).
• Subtask \(3\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

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

13
30

Cho dãy số \(A\) gồm \(N\) phần tử gồm các số nguyên dương \(A_1, A_2, ..., A_N\), và \(Q\) truy vấn, truy vấn thứ \(i\) gồm \(2\) số nguyên dương \(L_i, R_i\) \((1 \leq L_i \leq R_i \leq N)\).

Yêu cầu: Với mỗi truy vấn thứ \(i\), hãy đếm số phần tử phân biệt trong khoảng từ \(L_i\) tới \(R_i\).

Input

• Gồm \(Q+2\) dòng:
• Dòng thứ nhất chứa hai số nguyên dương \(N, Q\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((1 \leq A_i \leq 10^6)\).
• \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(L_i, R_i\).

Output

• In ra \(Q\) dòng, dòng thứ \(i\) là số phần tử phân biệt trong khoảng từ \(L_i\) tới \(R_i\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N, Q \leq 10^5\).

Example

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

3
2
3

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Cho \(Q\) thao tác, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(p_i\) \(x_i\): Thay giá trị ở vị trí \(p_i\) thành \(x_i\) (tức gán \(A_{p_i} = x_i\)).
• \(2\) \(u_i\) \(v_i\): Đếm số phần tử phân biệt và tính tổng các giá trị phân biệt trong đoạn từ \(u_i\) tới \(v_i\).

Yêu cầu: Thực hiện tất cả \(Q\) thao tác, và in ra \(2\) kết quả của thao tác loại \(2\).

Input

Gồm \(Q+2\) dòng:

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((A_i \leq 10^9)\).
• \(Q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi hai số nguyên dương \(p_i\), và \(x_i\) \((1 \leq p_i\leq N\), \(1 \leq x_i \leq 10^9)\). Số \(2\) theo sau bởi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \leq u_i \leq v_i \leq N)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra \(2\) kết quả lần lượt là số phần tử phân biệt và tính tổng các giá trị phân biệt trong đoạn từ \(u\) tới \(v\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(30\)% số điểm có \(N \leq 2.10^3\), \(Q \leq 2.10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 5.10^4\), \(Q \leq 5.10^4\), chỉ có các thao tác loại \(2\).
• Subtask \(3\) (\(40\%\) số điểm): \(N \leq 5.10^4\), \(Q \leq 5.10^4\).

Example

 3 3
1 2 3
2 1 3
1 3 2
2 2 3 

3 6
1 2

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\) (\(A_i \leq 10^9\)). Cho \(Q\) thao tác thực liện lần lượt, thao tác thứ \(i\) sẽ có một trong \(4\) loại như sau:

• \(1\) \(p_i\) \(x_i\): Chèn giá trị \(x_i\) vào giữa hai vị trí \(p_i - 1\) và \(p_i\) trong dãy \(A\) (\(1 \leq x_i \leq 10^9\), \(1 \leq p_i \leq T + 1\), với \(T\) là số phần tử hiện có trong dãy \(A\). Nếu \(p_i = T + 1\), chèn \(x_i\) vào cuối dãy \(A\)).
• \(2\) \(u_i\) \(l_i\) \(v_i\): Chuyển tất cả các phần tử liên tiếp, bắt đầu từ vị trí \(u_i\), kết thúc ở vị trí \(u_i + l_i - 1\), chèn vào trước vị trí \(v_i\) trong số còn lại (\(1 \leq u_i \leq T\), \(u_i + l_i - 1 \leq T\) \(1 \leq v_i \leq T - l_i + 1\), với \(T\) là số phần tử hiện có trong dãy \(A\). Nếu \(v_i = T - l_i + 1\) thì chuyển tất cả các phần tử liên tiếp, bắt đầu từ vị trí \(u_i\), kết thúc ở vị trí \(u_i + l_i - 1\) vào cuối dãy \(A\)).
• \(3\) \(p_i\): Xoá phần tử ở vị trí \(p_i\) (\(1 \leq p_i \leq T\), với \(T\) là số phần tử hiện có trong dãy \(A\)).
• \(4\) \(u_i\) \(v_i\): Tìm giá trị lớn nhất trong các phần tử từ vị trí \(u_i\) tới vị trí \(v_i\) (\(1 \leq u_i \leq v_i \leq T\), với \(T\) là số phần tử hiện có trong dãy \(A\)).

Yêu cầu
Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(4\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\).
• \(Q\) dòng tiếp theo, với dòng thứ \(i\) chứa một trong \(4\) thao tác:
  • \(1\) \(p_i\) \(x_i\).
  • \(2\) \(u_i\) \(l_i\) \(v_i\).
  • \(3\) \(p_i\).
  • \(4\) \(u_i\) \(v_i\).

Output

• Với thao tác loại \(4\) có dạng \(4\) \(u\) \(v\), in ra giá trị lớn nhất trong các phần tử từ vị trí \(u\) tới vị trí \(v\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3\), \(Q \leq 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\), chỉ có các thao tác loại \(4\).
• Subtask \(3\) (\(40\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\).

Example

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

3
5

Cho số nguyên \(A\) gồm \(N\) phần tử gồm các số nguyên dương \(A_1, A_2, ..., A_N\). Cho \(Q\) thao tác được thực hiện lần lượt bao gồm gán, truy vấn và quay lại: (Gọi \(T\) là số lần gán. Ban đầu \(T = 0\)).

• Thao tác gán có dạng: \(1\) \(p\) \(val\): Gán \(A_p = val\) (\(1 \leq p \leq N\), \(1 \leq val \leq 10^9\)). Và \(T\) sẽ tăng lên \(1\).
• Thao tác truy vấn có dạng: \(2\) \(u\) \(v\) \(t\): Tìm giá trị lớn nhất trong đoạn từ \(u\) tới \(v\) sau phép gán lần thứ \(t\) (\(1 \leq u \leq v \leq N\), \(0 \leq t \leq T\). Nếu \(t = 0\) thì sẽ truy vấn trên mảng ban đầu trước khi thực hiện \(Q\) thao tác).
• Thao tác quay lại có dạng: \(3\) \(t\): Quay lại thời điểm sau lần gán thứ \(t\) (\(0 \leq t \leq T\). Nếu \(t = 0\) thì sẽ quay về mảng ban đầu trước khi thực hiện \(Q\) thao tác). Mọi thao tác gán sau thời điểm \(t\) sẽ bị xoá bỏ. Và \(T = t\).

Yêu cầu

Thực hiện lần lượt \(Q\) thao tác. Với thao tác loại \(2\) (Truy vấn), in ra kết quả.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên dương \(N\) và \(Q\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) (\(A_i \leq 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng là một thao tác gán, truy vấn hoặc quay lại: \(1\) \(p\) \(val\) hoặc \(2\) \(u\) \(v\) \(t\) hoặc \(3\) \(t\).

Kết quả

Với thao tác loại \(2\), in ra kết quả trên một dòng.

Ràng buộc

• \(30\%\) số test đầu tiên tương đương với \(30\%\) số điểm có \(N, Q \leq 10^3\).
• \(30\%\) số test tiếp theo tương đương với \(30\%\) số điểm có \(N, Q \leq 10^5\), không có thao tác \(3\), mọi thao tác \(2\) có \(t = T\)
• \(40\%\) số test còn lại tương đương với \(40\%\) số điểm có \(N, Q \leq 10^5\).

Ví dụ

Input:

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

Output:

7
8
6
7

Chúa đất vùng rừng AnLuuLand sau khi cho người anh hùng algorit chọn một vùng đất đã nhận ra sai lầm của mình khi cho phép phá rừng để làm nương rẫy, làm giảm diện tích rừng gây ảnh hưởng lớn đến biến đổi khí hậu.

Để khắc phục hậu quả, chúa đất quyết định trồng cây vào khu vực trống trước đó. Khu vực trống có thể xem là một hình chữ nhật gồm \(m\) hàng và \(n\) cột. Ban đầu trên này chưa hề có cây. Chúa trồng lên mỗi ô một cây xanh, ban đầu mỗi cây cao \(1 cm\). Mỗi tuần chúa đất ra một trong hai lệnh theo thứ tự:

• \(1\) \(x\) \(y\) \(u\) \(v\) \(c\): Bón phân cho một khu hình chữ nhật: \((x, y, u, v, c)\) bón cho mỗi cây có tọa độ thuộc vào hình chữ nhật có góc trái trên là \((x,y\)) và góc phải dưới là \((u,v)\) thêm \(c\) (gr) phân bón. Mỗi cây xanh khi nhận được \(1\) (gr) phân bón sẽ cao thêm \(1 (cm).\)
• \(2\) \(x\) \(y\): Cho biết chiều cao của cây ở ô \((x, y)\).

Sau \(k\) tuần thực hiện, chúa đất muốn biết về tình trạng độ cao của cây xanh ở các lệnh dạng \(2\) trong khu vực này. Nhiệm vụ của bạn thống kê điều đó cho chúa đất.

Input

• Dòng thứ nhất gồm 3 số \(m, n , k\)
• \(k\) dòng sau, mỗi dòng gồm một trong \(2\) lệnh có dạng:
  • \(1\) \(x\) \(y\) \(u\) \(v\) \(c\) (\(1 \leq x \leq u \leq m\), \(1 \leq y \leq v \leq n\), \(1 \leq c \leq 10^6\)).
  • \(2\) \(x\) \(y\) (\(1 \leq x \leq m\), \(1 \leq y \leq n\)).

Output

• Với mỗi lệnh dạng \(2\), in ra số nguyên duy nhất trên một dòng.

Scoring

• Subtask #1 (\(30\%\) số điểm): \(m * n \leq 10^3, k \leq 10^3\)
• Subtask #2 (\(30\%\) số điểm): \(m * n \leq 10^5, k \leq 10^5\), các lệnh loại \(1\) luôn thực hiện trước các lệnh loại \(2\).
• Subtask #3 (\(40\%\) số điểm): \(m * n \leq 10^5, k \leq 10^5\)

Example

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

2
4
2

Chúa đất vùng rừng AnLuuLand sau khi cho người anh hùng algorit chọn một vùng đất đã nhận ra sai lầm của mình khi cho phép phá rừng để làm nương rẫy, làm giảm diện tích rừng gây ảnh hưởng lớn đến biến đổi khí hậu.

Để khắc phục hậu quả, chúa đất quyết định trồng cây vào khu vực trống trước đó. Khu vực trống có thể xem là một hình chữ nhật gồm \(m\) hàng và \(n\) cột. Ban đầu trên này chưa hề có cây. Chúa trồng lên mỗi ô một cây xanh, ban đầu mỗi cây cao \(1cm\). Mỗi tuần chúa đất ra một trong hai lệnh theo thứ tự:

• \(1\space x\space y\space u\space v\space c\): Bón phân cho một khu hình chữ nhật: \((x,y,u,v,c)\) bón cho mỗi cây có tọa độ thuộc vào hình chữ nhật có góc trái trên là \((x,y)\) và góc phải dưới là \((u,v)\) thêm \(c(gr)\) phân bón. Mỗi cây xanh khi nhận được \(1(gr)\) phân bón sẽ cao thêm \(1(cm)\).
• \(2\space x\space y\): Cho biết chiều cao cây có toạ độ \((x,y)\).

Sau \(k\) tuần thực hiện, chúa đất muốn biết về tình trạng độ cao của cây xanh ở các lệnh dạng \(2\) trong khu vực này. Nhiệm vụ của bạn thống kê điều đó cho chúa đất.

Input

• Dòng thứ nhất gồm 3 số nguyên \(m,n,k\).
• \(k\) dòng tiếp theo, mỗi dòng gồm \(1\) trong \(2\) lệnh có dạng:
  1 x y u v c (\(1 \leq x \leq u \leq m,1 \leq y \leq v \leq n,1 \leq c \leq 10^6\)).
  2 x y (\(1 \leq x \leq m,1 \leq y \leq n\)).

Output

• Với mỗi lệnh dạng \(2\), in ra số nguyên duy nhất trên một dòng.

Constraints

• \(1 \leq k \leq 10^5\)
• \(1 \leq m,n \leq 10^5\)

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m*n \leq 10^3, k \leq 10^3\).
• Subtask \(2\) (\(20\%\) số điểm): \(m*n \leq 10^5, k \leq 10^5\).
• Subtask \(3\) (\(20\%\) số điểm): \(m,n \leq 10^5, k \leq 10^5\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

2
4
2

Chúa đất vùng rừng AnLuuLand sau khi cho người anh hùng algorit chọn một vùng đất đã nhận ra sai lầm của mình khi cho phép phá rừng để làm nương rẫy, làm giảm diện tích rừng gây ảnh hưởng lớn đến biến đổi khí hậu.

Để khắc phục hậu quả, chúa đất quyết định trồng cây vào khu vực trống trước đó. Khu vực trống có thể xem là một hình chữ nhật gồm \(m\) hàng và \(n\) cột. Ban đầu trên này chưa hề có cây. Chúa trồng lên mỗi ô một cây xanh, ban đầu mỗi cây cao \(1 cm\). Mỗi tuần chúa đất ra một trong hai lệnh theo thứ tự:

• \(1\) \(x\) \(y\) \(u\) \(v\) \(c\): Bón phân cho một khu hình chữ nhật: \((x, y, u, v, c)\) bón cho mỗi cây có tọa độ thuộc vào hình chữ nhật có góc trái trên là \((x,y\)) và góc phải dưới là \((u,v)\) thêm \(c\) (gr) phân bón. Mỗi cây xanh khi nhận được \(1\) (gr) phân bón sẽ cao thêm \(1 (cm).\)
• \(2\) \(x\) \(y\) \(u\) \(v\): Cho biết tổng tất cả chiều cao các cây có toạ độ thuộc hình chữ nhật có góc trái trên là \((x,y\)) và góc phải dưới là \((u,v)\).

Sau \(k\) tuần thực hiện, chúa đất muốn biết về tình trạng độ cao của cây xanh ở các lệnh dạng \(2\) trong khu vực này. Nhiệm vụ của bạn thống kê điều đó cho chúa đất.

Input

• Dòng thứ nhất gồm 3 số \(m, n , k\).
• \(k\) dòng sau, mỗi dòng gồm một trong \(2\) lệnh có dạng:
  • \(1\) \(x\) \(y\) \(u\) \(v\) \(c\) (\(1 \leq x \leq u \leq m\), \(1 \leq y \leq v \leq n\), \(1 \leq c \leq 10^3\)).
  • \(2\) \(x\) \(y\) \(u\) \(v\) (\(1 \leq x \leq u \leq m\), \(1 \leq y \leq v \leq n\)).

Output

• Với mỗi lệnh dạng \(2\), in ra số nguyên duy nhất trên một dòng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m, n \leq 10^2, k \leq 10^3\).
• Subtask \(2\) (\(20\%\) số điểm): \(m, n \leq 10^3, k \leq 10^5\), các lệnh loại \(1\) luôn thực hiện trước các lệnh loại \(2\).
• Subtask \(3\) (\(20\%\) số điểm): \(m, n \leq 10^3, k \leq 10^5\), các lệnh loại \(1\) luôn có \(x = u\), \(y = v\).
• Subtask \(4\) (\(20\%\) số điểm): \(m, n \leq 10^3, k \leq 10^5\), các lệnh loại \(2\) luôn có \(x = u\), \(y = v\).
• Subtask \(5\) (\(20\%\) số điểm): \(m, n \leq 10^3, k \leq 10^5\).

Example

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

18
4
48

Có \(n\) khách sạn trên một con đường. Với mỗi khách sạn bạn biết được số phòng còn trống. Nhiệm vụ của bạn là chỉ định các phòng khách sạn cho \(m\) nhóm khách du lịch. Tất cả các thành viên trong cùng một nhóm muốn trọ chung một khách sạn.

Các nhóm sẽ lần lượt đến và bạn biết số phòng yêu cầu của mỗi nhóm. Với mỗi nhóm, bạn luôn tìm khách sạn đầu tiên mà đủ số phòng trống và chỉ định nhóm đấy vào phòng này. Sau đó, số phòng trống của khách sạn này sẽ giảm đi.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n\), \(m\): Số khách sạn và số nhóm. Các khách sạn được đánh số theo thứ tự từ \(1\) tới \(n\)
• Dòng thứ hai gồm \(n\) số nguyên dương \(h_1,h_2,...,h_n\): số phòng trống của mỗi khách sạn
• Dòng cuối cùng gồm \(m\) số nguyên dương \(r_1,r_2,...,r_m\): số phòng trống mà mỗi nhóm yêu cầu

Constraints

• \(1 \leq n,m \leq 2\cdot 10^5\)
• \(1 \leq h_i \leq 10^9\)
• \(1 \leq r_i \leq 10^9\)

Output

• In ra \(m\) số nguyên là chỉ số của khách sạn được phân cho mỗi nhóm. Nếu nhóm nào đó không được chỉ định vào khách sạn (do không tìm được), in ra số \(0\)

Example

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

3 5 0 1 1

Cho một mảng gồm \(N\) phần tử là các số nguyên. Nhiệm vụ của bạn là xoá phần tử trong mảng và báo cáo phần tử đã bị xoá.

Input

• Dòng đầu tiên gồm số nguyên dương \(N\): kích thước mảng ban đầu. Sau khi xoá một phần tử, các phần tử còn lại sẽ được đánh số lại từ \(1\) tới \(k\), với \(k\) là kích thước mảng hiện tại.
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1,A_2,...,A_N\) \((1≤A_i≤10^9)\).
• Dòng cuối cùng gồm \(N\) số nguyên dương \(P_1,P_2,...,P_N\) \((1≤P_i≤N−i+1)\): vị trí của phần tử bị xoá.

Output

• In ra phần tử bị xoá theo thứ tự.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N,Q≤2.10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N,Q≤2.10^5\).

Example

5
2 6 1 4 2
3 1 3 1 1 

1 2 2 6 4

Một công ty có \(N\) nhân viên với với mức lương nhất định. Nhiệm vụ của bạn là theo dõi mức lương và thực hiện truy vấn.

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\) là số nhân viên và số truy vấn. Các nhân viên được đánh số từ \(1\) tới \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) là lương của mỗi người.
• \(Q\) dòng tiếp theo, mỗi dòng gồm một truy vấn thuộc một trong hai dạng sau:
• \(!\) \(k\) \(x\): thay đổi lương của người thứ \(k\) thành \(x\).
• \(?\) \(a\) \(b\): đếm số người có mức lương từ \(a\) tới \(b\).

Output

• In ra kết quả cho truy vấn \(?\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N, Q \leq 2.10^3\), \(1 \leq A_i \leq 10^9\) với \(\forall i, 1 \leq i \leq N\).
• Subtask \(2\) (\(30\%\) số điểm): \(N, Q \leq 2.10^5\), \(1 \leq A_i \leq 10^5\) với \(\forall i, 1 \leq i \leq N\).
• Subtask \(3\) (\(40\%\) số điểm): \(N, Q \leq 2.10^5\), \(1 \leq A_i \leq 10^9\) với \(\forall i, 1 \leq i \leq N\).

Example

5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3 

3
2

Cho một mảng bao gồm \(N\) số nguyên. Một số phần tử sẽ được cập nhật, và sau mỗi lần cập nhật, nhiệm vụ của bạn là tìm tổng lớn nhất của tất cả các đoạn con (liên tiếp) trong mảng.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N, Q\): Kích thước của mảng và số truy vấn.
• Dòng thứ hai gồm \(N\) số nguyên \(A_1, A_2, ..., A_N\) \((|A_i| \leq 10^9)\).
• \(Q\) dòng tiếp theo, mỗi dòng có hai số nguyên \(k\) và \(x\) \((1 \leq k \leq N, |x| \leq 10^9)\): thay đổi phần tử \(k\) thành giá trị \(x\).

Output

• Sau mỗi lần cập nhật, in ra tổng lớn nhất của tất cả các đoạn con trong mảng. Các mảng con rỗng (với tổng bằng 0) vẫn được tính.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 2.10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N, Q \leq 2.10^5\).

Example

5 3
1 2 -3 5 -1
2 6
3 1
2 -2 

9
13
6

Cho mảng gồm \(N\) phần tử là các số nguyên. Nhiệm vụ của bạn là xử lý các loại truy vấn sau:

• \(1\) \(a\) \(b\) \(x\) : Tăng các phần tử từ \(a\) đến \(b\) lên \(x\).
• \(2\) \(a\) \(b\) \(x\) : Thay đổi tất cả các phần tử từ \(a\) đến \(b\) thành \(x\).
• \(3\) \(a\) \(b\) : Tính tổng các phần tử từ \(a\) đến \(b\).

Input

• Dòng thứ nhất gồm hai số nguyên \(N, Q\) là kích thước mảng và số truy vấn.
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((1 \leq A_i \leq 10^6)\).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn thuộc một trong ba dạng sau:
  • \(1\) \(a\) \(b\) \(x\) \((1 \leq a \leq b \leq N, 1 \leq x \leq 10^6)\).
  • \(2\) \(a\) \(b\) \(x\) \((1 \leq a \leq b \leq N, 1 \leq x \leq 10^6)\).
  • \(3\) \(a\) \(b\) \((1 \leq a \leq b \leq N)\).

Output

• In ra kết quả cho các truy vấn \(3\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 2.10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N, Q \leq 2.10^5\).

Example

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

7
11
15

Bạn được cho một mảng \(a\) gồm \(n\) phần tử và \(q\) truy vấn. Có 2 loại truy vấn:

• Loại 1: có dạng \(1\) \(a\) \(b\): Tăng phần tử thứ nhất trong đoạn \([a, b]\) lên 1 đơn vị, phần tử thứ 2 lên 2 đơn vị, và cứ thế đến hết.
• Loại 2: có dạng \(2\) \(a\) \(b\): Tính tổng tất cả các phần tử trong đoạn \([a, b]\)

Input

• Dòng thứ nhất gồm 2 số \(n\) và \(q\)
• Dòng thứ 2 gồm \(n\) phần tử của mảng \(a\)
• \(q\) dòng còn lại, mỗi dòng là 1 truy vấn thuộc loại 1 hoặc 2

Constraints

• \(1 \leq n, q \leq 2\cdot 10^5\)
• \(1 \leq a_i \leq 10^6\)
• \(1 \leq a, b \leq n\)

Output

• Với mỗi truy vấn loại 2, in ra tổng của các phần tử trong đoạn \([a, b]\)
• Mỗi đáp án đều được in trên một dòng

Example

5 3
4 2 3 1 7
2 1 5
1 1 5
2 1 5

17
32

Nhiệm vụ của bạn là duy trì một danh sách các mảng, danh sách ban đầu chỉ có một mảng duy nhất. Bạn phải xử lý các loại truy vấn sau:

1. Gán giá trị \(a\) trong mảng \(k\) thành \(x\).
2. Tính tổng các giá trị trong đoạn \([a,b]\) trong mảng \(k\).
3. Tạo một bản sao của mảng \(k\) và thêm nó vào cuối danh sách.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\): kích thước của mảng và số lượng truy vấn.
• Dòng tiếp theo chứa \(n\) số nguyên \(t_1, t_2, \dots, t_n\): các giá trị ban đầu của mảng.
• \(q\) dòng cuối cùng mô tả các truy vấn. Định dạng của từng truy vấn là một trong các kiểu sau: 1 k a x, 2 k a b hoặc 3 k.

Constraints

• \(1 \le n, q \le 2 \times 10^5\)
• \(1 \le t_i, x \le 10^9\)
• \(1 \le a \le b \le n\)

Output

• In ra kết quả của từng truy vấn tính tổng.

Example

5 6
2 3 1 2 5
3 1
2 1 1 5
2 2 1 5
1 2 2 5
2 1 1 5
2 2 1 5

13
13
13
15

Nông dân V.H.A có \(N\) khu vườn để chăn nuôi chú gà SPyofgame. Các khu vườn được kết nối với nhau bằng \(N-1\) con đường hai chiều, tức là chỉ có đúng một đường đi giữa hai khu vườn (giàu mà keo đây mà). Vì là một con gà béo tham lam nên SPyofgame đã đòi hỏi trên đường các con đường luôn phải có đồ ăn cho nó. Vì thế, V.H.A đã phải thực hiện các công việc sau:

1. P x y: V.H.A sẽ chọn ra hai khu vườn và bỏ 1 nồi thóc dọc theo con đường nối hai khu vườn.
2. Q x y: V.H.A sẽ phải trả lời trên đoạn đường nối hai khu vườn có bao nhiêu nồi thóc.

Input:

• Dòng đầu tiên chứa hai số nguyên \(N, M (1 \leq M \leq 100000, 2 \leq N \leq 100000).\)
• \(N-1\) dòng tiếp theo, mỗi dòng là hai số nguyên thể hiện hai đầu nối của một con đường.
• \(M\) dòng cuối cùng, mỗi dòng là một truy vấn theo cấu trúc P x y hoặc Q x y \((1 \leq x,y \leq N)\).

Output:

• Mỗi dòng là câu trả lời cho mỗi truy vấn Q theo thứ tự.

Example

3 3
1 2
2 3
P 1 3
Q 2 3
Q 1 3

1
2

Chúa đất vùng rừng AnLuuLand sau khi cho người anh hùng algorit chọn một vùng đất đã nhận ra sai lầm của mình khi cho phép phá rừng để làm nương rẫy, làm giảm diện tích rừng gây ảnh hưởng lớn đến biến đổi khí hậu.

Để khắc phục hậu quả, chúa đất quyết định trồng cây vào khu vực trống trước đó. Khu vực trống có thể xem là một hình chữ nhật gồm \(m\) hàng và \(n\) cột. Ban đầu trên này chưa hề có cây. Chúa trồng lên mỗi ô một cây xanh, ban đầu mỗi cây cao \(1cm\). Mỗi tuần chúa đất ra một trong hai lệnh theo thứ tự:

• \(1\space x\space y\space u\space v\space c\): Bón phân cho một khu hình chữ nhật: \((x,y,u,v,c)\) bón cho mỗi cây có tọa độ thuộc vào hình chữ nhật có góc trái trên là \((x,y)\) và góc phải dưới là \((u,v)\) thêm \(c(gr)\) phân bón. Mỗi cây xanh khi nhận được \(1(gr)\) phân bón sẽ cao thêm \(1(cm)\).
• \(2\space x\space y\space u\space v\): Cho biết tổng tất cả chiều cao các cây có toạ độ thuộc hình chữ nhật có góc trái trên là \((x,y)\) và góc phải dưới là \((u,v)\).

Sau \(k\) tuần thực hiện, chúa đất muốn biết về tình trạng độ cao của cây xanh ở các lệnh dạng \(2\) trong khu vực này. Nhiệm vụ của bạn thống kê điều đó cho chúa đất.

Input

• Dòng thứ nhất gồm 3 số \(m,n,k\).
• \(k\) dòng sau, mỗi dòng gồm một trong \(2\) lệnh có dạng:
  • \(1\space x\space y\space u\space v\space c\) \((1≤x≤u≤m, 1≤y≤v≤n, 1≤c≤10^3)\).
  • \(2\space x\space y\space u\space v\) \((1≤x≤u≤m, 1≤y≤v≤n,)\).

Output

• Với mỗi lệnh dạng \(2\), in ra số nguyên duy nhất trên một dòng.

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(m,n≤10^2,k≤10^3\).
• Subtask \(2\) (\(15\%\) số điểm): \(m,n≤10^3,k≤10^5\), các lệnh loại \(1\) luôn được thực hiện trước các câu lệnh loại \(2\).
• Subtask \(3\) (\(10\%\) số điểm): \(m,n≤10^3,k≤10^5\), các lệnh loại \(1\) luôn có \(x = u, y = v\).
• Subtask \(4\) (\(10\%\) số điểm): \(m,n≤10^3,k≤10^5\), các lệnh loại \(2\) luôn có \(x = u, y = v\).
• Subtask \(5\) (\(15\%\) số điểm): \(m,n≤10^3,k≤10^5\).
• Subtask \(6\) (\(15\%\) số điểm): \(m,n≤10^5,k≤10^5\).

Example

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

18
4
48

Jian-Jia đang lên kế hoạch cho kỳ nghỉ tiếp theo tại Đài Loan. Trong kỳ nghỉ, cậu di chuyển giữa các thành phố và tham quan các điểm du lịch trong những thành phố đó.

Có \(n\) thành phố, tất cả nằm dọc theo một con đường cao tốc, được đánh số liên tiếp từ \(0\) đến \(n-1\). Với thành phố \(i\) thỏa mãn \(0<i<n-1\), hai thành phố liền kề là \(i-1\) và \(i+1\). Thành phố duy nhất liền kề với thành phố 0 là thành phố 1; thành phố duy nhất liền kề với thành phố \(n-1\) là thành phố \(n-2\).

Mỗi thành phố có một số điểm du lịch. Jian-Jia có \(d\) ngày nghỉ và muốn tham quan nhiều điểm du lịch nhất có thể. Cậu đã chọn sẵn thành phố xuất phát. Trong mỗi ngày, Jian-Jia hoặc di chuyển đến một thành phố liền kề, hoặc tham quan tất cả các điểm du lịch của thành phố đang ở, nhưng không thể làm cả hai. Jian-Jia không bao giờ tham quan các điểm du lịch trong cùng một thành phố hai lần, ngay cả khi cậu đến thành phố đó nhiều lần. Hãy giúp cậu lập kế hoạch để tham quan được nhiều điểm du lịch khác nhau nhất.

Ví dụ

Giả sử Jian-Jia có 7 ngày nghỉ, có 5 thành phố với số điểm du lịch như bảng dưới đây, và cậu xuất phát từ thành phố 2.

Thành phố  Số điểm du lịch
0          10
1          2
2          20
3          30
4          1

Ngày thứ nhất, Jian-Jia tham quan 20 điểm du lịch ở thành phố 2. Ngày thứ hai, cậu di chuyển từ thành phố 2 đến thành phố 3. Ngày thứ ba, cậu tham quan 30 điểm du lịch ở thành phố 3. Cậu dùng ba ngày tiếp theo để đi từ thành phố 3 đến thành phố 0, rồi tham quan 10 điểm du lịch ở thành phố 0 vào ngày thứ bảy.

Ngày  Hoạt động
1     Tham quan các điểm du lịch ở thành phố 2
2     Di chuyển từ thành phố 2 đến thành phố 3
3     Tham quan các điểm du lịch ở thành phố 3
4     Di chuyển từ thành phố 3 đến thành phố 2
5     Di chuyển từ thành phố 2 đến thành phố 1
6     Di chuyển từ thành phố 1 đến thành phố 0
7     Tham quan các điểm du lịch ở thành phố 0

Tổng số điểm du lịch được tham quan là

Đây là số điểm du lịch lớn nhất có thể tham quan trong 7 ngày nếu xuất phát từ thành phố 2.

Nhiệm vụ

Hãy cài đặt hàm findMaxAttraction(n, start, d, attraction) để tính số điểm du lịch lớn nhất Jian-Jia có thể tham quan.

• n: số thành phố.
• start: chỉ số thành phố xuất phát.
• d: số ngày nghỉ.
• attraction: mảng độ dài \(n\); attraction[i] là số điểm du lịch ở thành phố \(i\), với \(0 \le i \le n-1\).
• Hàm phải trả về số điểm du lịch lớn nhất Jian-Jia có thể tham quan.

Các subtasks

Trong tất cả các subtasks, số điểm du lịch ở mỗi thành phố là không âm và

Các ràng buộc bổ sung:

Chi tiết cài đặt

Bạn phải nộp đúng một tệp có tên holiday.c, holiday.cpp hoặc holiday.pas, cài đặt chương trình con theo đặc tả trên và chữ ký dưới đây. Với C/C++, bạn phải nạp tệp tiêu đề holiday.h.

Lưu ý: kết quả có thể rất lớn; kiểu trả về của findMaxAttraction là số nguyên 64 bit.

C/C++:

long long int findMaxAttraction(int n, int start, int d,
int attraction[]);

Pascal:

function findMaxAttraction(n, start, d : longint;
attraction : array of longint): int64;

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng 1: n, start, d.
• Dòng 2: attraction[0], ..., attraction[n-1].

Trình chấm mẫu in giá trị trả về của findMaxAttraction.

Jian-Jia đang xây một bức tường bằng cách xếp các viên gạch cùng kích thước. Bức tường gồm \(n\) cột gạch, được đánh số từ \(0\) đến \(n-1\) từ trái sang phải. Các cột có thể cao khác nhau. Độ cao của một cột là số viên gạch trong cột đó.

Ban đầu, tất cả các cột đều không có gạch. Sau đó, Jian-Jia thực hiện \(k\) giai đoạn thêm hoặc bớt gạch. Quá trình xây dựng kết thúc khi hoàn thành cả \(k\) giai đoạn. Trong mỗi giai đoạn, Jian-Jia được cho một dãy cột liên tiếp và một độ cao \(h\), rồi thực hiện như sau:

• Trong giai đoạn thêm, với mỗi cột thuộc dãy đã cho có ít hơn \(h\) viên gạch, Jian-Jia thêm gạch để cột có đúng \(h\) viên. Các cột có từ \(h\) viên trở lên không thay đổi.
• Trong giai đoạn bớt, với mỗi cột thuộc dãy đã cho có nhiều hơn \(h\) viên gạch, Jian-Jia bớt gạch để cột có đúng \(h\) viên. Các cột có từ \(h\) viên trở xuống không thay đổi.

Nhiệm vụ của bạn là xác định hình dạng cuối cùng của bức tường.

Ví dụ

Giả sử có 10 cột gạch và 6 giai đoạn xây dựng. Mọi dãy cột trong bảng dưới đây đều bao gồm cả hai đầu mút.

Giai đoạn  Kiểu  Dãy cột        Độ cao
0          thêm  từ cột 1 đến 8  4
1          bớt   từ cột 4 đến 9  1
2          bớt   từ cột 3 đến 6  5
3          thêm  từ cột 0 đến 5  3
4          thêm  cột 2           5
5          bớt   từ cột 6 đến 7  0

Do ban đầu tất cả các cột đều rỗng, sau giai đoạn 0, mỗi cột từ 1 đến 8 có 4 viên gạch; các cột 0 và 9 vẫn rỗng. Trong giai đoạn 1, gạch được bớt khỏi các cột từ 4 đến 8 cho đến khi mỗi cột còn đúng 1 viên; cột 9 vẫn rỗng. Các cột từ 0 đến 3 nằm ngoài dãy đã cho nên không đổi. Giai đoạn 2 không làm thay đổi gì vì các cột từ 3 đến 6 không có nhiều hơn 5 viên gạch. Sau giai đoạn 3, số gạch trong các cột 0, 4 và 5 tăng lên thành 3. Sau giai đoạn 4, cột 2 có 5 viên gạch. Giai đoạn 5 loại bỏ tất cả gạch ở các cột 6 và 7.

Các hình dưới đây lần lượt mô tả bức tường sau từng giai đoạn.

Sau giai đoạn 0:

Sau giai đoạn 1:

Sau giai đoạn 2 (không thay đổi):

Sau giai đoạn 3:

Sau giai đoạn 4:

Sau giai đoạn 5:

Nhiệm vụ

Cho mô tả của \(k\) giai đoạn, hãy tính số viên gạch trong mỗi cột sau khi hoàn thành tất cả các giai đoạn. Bạn cần cài đặt hàm buildWall(n, k, op, left, right, height, finalHeight).

• n: số cột của bức tường.
• k: số giai đoạn.
• op: mảng độ dài \(k\); op[i] là kiểu của giai đoạn \(i\): 1 là thêm, 2 là bớt, với \(0 \le i \le k-1\).
• left, right: hai mảng độ dài \(k\); dãy cột của giai đoạn \(i\) bắt đầu tại left[i] và kết thúc tại right[i], bao gồm cả hai đầu mút, với \(0 \le i \le k-1\). Luôn có left[i] \(\le\) right[i].
• height: mảng độ dài \(k\); height[i] là thông số độ cao của giai đoạn \(i\), với \(0 \le i \le k-1\).
• finalHeight: mảng độ dài \(n\); bạn phải gán số viên gạch cuối cùng trong cột \(i\) vào finalHeight[i], với \(0 \le i \le n-1\).

Các subtasks

Trong mọi subtask, thông số độ cao ở mọi giai đoạn là số nguyên không âm không lớn hơn \(100\,000\).

Chi tiết cài đặt

Bạn phải nộp đúng một tệp có tên wall.c, wall.cpp hoặc wall.pas, cài đặt chương trình con theo đặc tả trên và chữ ký dưới đây. Với C/C++, bạn phải nạp tệp tiêu đề wall.h.

C/C++:

void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]);

Pascal:

procedure buildWall(n, k : longint; op, left, right, height :
array of longint; var finalHeight : array of longint);

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng 1: n, k.
• Dòng \(2+i\), với \(0 \le i \le k-1\): op[i], left[i], right[i], height[i].