Dãy con liên tiếp có tổng lớn nhất trên phiên bản
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho mảng $a_1,\dots,a_n$ (phiên bản $0$). Các thao tác (mỗi thao tác loại $1$ tạo phiên bản mới có số hiệu tiếp theo):
1 v i x: tạo phiên bản mới từ phiên bản $v$ bằng cách gán $a_i=x$.2 v l r: in tổng lớn nhất của một đoạn con không rỗng $a_i+\dots+a_j$ với $l\le i\le j\le r$ trong phiên bản $v$.
Dữ liệu vào
Dòng đầu: $n,q$. Dòng hai: $n$ số nguyên. Sau đó $q$ dòng thao tác.
Dữ liệu ra
Với mỗi thao tác loại $2$ in đáp án.
Ví dụ
Input
5 5
4 1 -9 8 -7
2 0 3 4
1 0 5 3
1 0 5 2
1 0 4 6
2 3 2 5
Output
8
6
Giới hạn
- $1\le n,q\le 10^5$; $|a_i|,|x|\le 10^9$.
- Thời gian: 2 giây; bộ nhớ: 256 MB.
Community Discussion