Không gian phân mảnh

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 2100 Thời gian: 0.25s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Hệ thống không gian không phải là một mạng lưới tuyến tính mà là một cấu trúc cây khổng lồ gồm \(N\) trạm trung chuyển. Mỗi trạm \(i\) chứa một lõi năng lượng có giá trị \(A_i\) (có thể âm nếu trạm bị rò rỉ phản vật chất). Cổng dịch chuyển của Prototype liên tục nhận được các bản cập nhật nhiễu loạn từ vũ trụ, làm thay đổi năng lượng của một trạm bất kỳ. uou cần Prototype liên tục trả lời các truy vấn: "Nếu đi từ trạm \(U\) đến trạm \(V\) trên con đường ngắn nhất, tổng năng lượng của một chuỗi các trạm liên tiếp lớn nhất trên đường đi đó là bao nhiêu?".

Yêu cầu: Cho một cây gồm \(N\) đỉnh. Mỗi đỉnh \(i\) có trọng số \(A_i\). Bạn cần xử lý \(Q\) truy vấn thuộc 2 loại:

Loại 1 u x:

Cập nhật trọng số của đỉnh \(u\) thành \(x\).

Loại 2 u v:

Tìm mảng con liên tiếp có tổng lớn nhất trên đường đi đơn từ đỉnh \(u\) đến đỉnh \(v\). Nếu tổng lớn nhất nhỏ hơn 0, in ra 0.

Input

Dòng 1: Chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)) — lần lượt là số lượng trạm trung chuyển và số lượng truy vấn.
Dòng 2: Chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^4 \le A_i \le 10^4\)) — mức năng lượng ban đầu tại mỗi trạm trung chuyển.
\(Q\) dòng tiếp theo: Mỗi dòng là một truy vấn thuộc một trong hai loại:
- Loại 1: 1 u x: Cập nhật mức năng lượng tại trạm \(u\) thành \(x\) (\(-10^4 \le x \le 10^4\)).
- Loại 2: 2 u v: Truy vấn tìm năng lượng lớn nhất của một chuỗi trạm
  liên tiếp trên đường đi đơn từ trạm \(u\) đến trạm \(v\).

Output

Với mỗi truy vấn loại 2, in ra một số nguyên duy nhất trên một dòng là tổng năng lượng lớn nhất tìm được. Nếu tất cả các chuỗi trạm trên đường đi đều có tổng năng lượng âm, in ra 0.

Example

Test 1

Input

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

Output

Note

Cấu trúc cây ban đầu và mức năng lượng tại các đỉnh:

Đỉnh 1: 1
Đỉnh 2: -2
Đỉnh 3: 3
Đỉnh 4: 4
Đỉnh 5: -1
Liên kết: 1-2, 2-3, 2-4, 1-5.

Chi tiết các truy vấn:

2 3 4: Đường đi từ 3 đến 4 là \(3 \rightarrow 2 \rightarrow 4\). Dãy giá trị trên đường đi: \([3, -2, 4]\).
- Các chuỗi liên tiếp có thể: \([3], [-2], [4], [3, -2], [-2, 4], [3, -2, 4]\).
- Tổng tương ứng: 3, -2, 4, 1, 2, 5.
- Tổng lớn nhất là 5 (chọn toàn bộ chuỗi \(3 \rightarrow 2 \rightarrow 4\)). In ra 5.
2 3 5: Đường đi từ 3 đến 5 là \(3 \rightarrow 2 \rightarrow 1 \rightarrow 5\). Dãy giá trị: \([3, -2, 1, -1]\).
- Chuỗi liên tiếp có tổng lớn nhất là \([3]\) tại đỉnh 3.
  Tổng lớn nhất là 3. In ra 3.
2 5 5: Đường đi từ 5 đến 5 chỉ có chính nó 5. Dãy giá trị: \([-1]\).
- Vì giá trị âm, theo luật năng lượng không được phép dưới mức 0, ta không chọn trạm nào. In ra 0.
1 2 5: Cập nhật năng lượng tại đỉnh 2 thành 5. Dãy năng lượng mới của 5 đỉnh: \(1, 5, 3, 4, -1\).
2 3 4: Đường đi từ 3 đến 4 vẫn là \(3 \rightarrow 2 \rightarrow 4\). Dãy giá trị lúc này: \([3, 5, 4]\).
- Chuỗi liên tiếp lớn nhất là toàn bộ dãy \([3, 5, 4]\).
- Tổng lớn nhất: \(3 + 5 + 4 = 12\). In ra 12.

Scoring

\(N, Q \le 10^5\)
\(-10^4 \le A_i, x \le 10^4\)
Subtask 1 (20%): \(N, Q \le 1000\).
Subtask 2 (30%): Cây có dạng đường thẳng (mỗi đỉnh bậc tối đa là 2).
Subtask 3 (50%): Không có ràng buộc gì thêm.

Bình luận (3)

Tải bình luận...