Dãy con liên tiếp có tổng lớn nhất trên phiên bản

Buổi 30 — Persistent Segment Tree
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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.
Draft saved