Tổng đoạn con lớn nhất với cập nhật

Algorithms Buổi 65-66 — Mock HSG Data-structures Dynamic Programming
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho dãy gồm $N$ số nguyên $A_1, A_2, \dots, A_N$ và $Q$ truy vấn thuộc một trong hai loại sau:

  • 1 idx val: Gán $A_{idx} = val$.
  • 2 l r: Tìm tổng lớn nhất của một đoạn con liên tiếp khác rỗng nằm hoàn toàn trong $[l, r]$.
Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, Q$.
  • Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$.
  • $Q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn.
Dữ liệu ra

Với mỗi truy vấn loại 2, in ra tổng đoạn con lớn nhất tìm được trên một dòng.

Ví dụ
Input Output
5 3
-2 1 -3 4 -1
2 1 5
1 3 5
2 1 5
4
10
Giới hạn

$1 \le N, Q \le 10^5$, $|A_i|, |val| \le 10^9$.

Draft saved