Bộ phân tích đoạn hợp nhất

Bối cảnh và bài toán

Một hệ thống phân tích lưu một dãy số động. Sau mỗi cập nhật điểm, bộ phận vận hành có thể hỏi tổng hoặc giá trị nhỏ nhất trên cùng một đoạn. Mục tiêu không chỉ là AC mà còn phải giải thích cấu trúc dữ liệu nào phù hợp nhất với operation profile này.

Yêu cầu

Xử lý SET, SUM, MIN theo đúng thứ tự.

Input

• Dòng 1 chứa n q.
• Dòng 2 chứa n số.
• SET i x: gán a[i]=x.
• SUM l r: hỏi tổng [l,r].
• MIN l r: hỏi min [l,r].

Output

In kết quả cho mỗi truy vấn SUM hoặc MIN.

Ràng buộc

• 1 <= n, q <= 2 * 10^5
• -10^9 <= a[i], x <= 10^9
• Chỉ số hợp lệ và l <= r.

Chấm điểm

Ví dụ 1

Input

5 6
3 1 4 1 5
SUM 1 5
MIN 2 4
SET 2 10
SUM 1 3
MIN 1 5
SUM 2 2

Output

14
1
17
1
10

Giải thích. Cùng một cấu trúc phải hỗ trợ hai phép combine khác nhau trên mỗi node.

Ví dụ 2

Input

3 4
-1 -2 -3
MIN 1 3
SUM 1 3
SET 3 5
SUM 2 3

Output

-3
-6
3

Giải thích. Dữ liệu âm kiểm tra identity của SUM và MIN.

Thông tin bài tập

• Yêu cầu ngoài OJ: nộp Decision Note theo template đi kèm.

Nguồn: FULLHOUSE DEV – Self-generated.