Editorial: Mathematical Algorithms TWK Open Problem #B - Bài toán cuối cấp

1. Ý tưởng

Bài toán yêu cầu thực hiện hai loại thao tác trên mảng \(a\):

1. Cập nhật phần tử tại vị trí \(i\) thành \(x\).
2. Tìm giá trị \(a[j] - a[i]\) lớn nhất sao cho \(l \le i < j \le r\).

Vì \(N, Q \le 5 \times 10^5\), các thuật toán duyệt \(O(N)\) cho mỗi truy vấn sẽ bị TLE. Do đó, ta cần sử dụng cấu trúc dữ liệu Segment Tree (Cây phân đoạn) để xử lý cả hai thao tác cập nhật và truy vấn trong thời gian \(O(\log N)\).

Mỗi nút trên Segment Tree quản lý một đoạn \([l, r]\) và lưu trữ 3 thông tin:

• mn: Giá trị nhỏ nhất trong đoạn \([l, r]\).
• mx: Giá trị lớn nhất trong đoạn \([l, r]\).
• ans: Mức tăng lớn nhất \(a[j] - a[i]\) với \(l \le i < j \le r\) trong đoạn đó.

Hàm hợp nhất (Merge) hai nút con (L và R):

Xét một đoạn \([l, r]\) được chia làm 2 nút con \(L\) (đoạn trái) và \(R\) (đoạn phải):

• res.mn = min(L.mn, R.mn)
• res.mx = max(L.mx, R.mx)
• Cặp vị trí \((i, j)\) cho mức tăng lớn nhất có thể rơi vào 1 trong 3 trường hợp:
• Cả \(i\) và \(j\) đều nằm ở đoạn bên trái \(L\) \(\rightarrow\) Đáp án là L.ans.
• Cả \(i\) và \(j\) đều nằm ở đoạn bên phải \(R\) \(\rightarrow\) Đáp án là R.ans.
• \(i\) nằm ở đoạn trái \(L\) và \(j\) nằm ở đoạn phải \(R\) \(\rightarrow\) Để tối ưu hiệu \(a[j] - a[i]\), ta chọn \(a[i]\) nhỏ nhất ở đoạn \(L\) (L.mn) và \(a[j]\) lớn nhất ở đoạn \(R\) (R.mx). Đáp án là R.mx - L.mn.

Do đó:
res.ans = max({L.ans, R.ans, R.mx - L.mn})

Xử lý các trường hợp đặc biệt:

• Với nút lá quản lý đoạn gồm 1 phần tử (chiều dài bằng 1), do không tồn tại cặp \(i < j\) nên gán ans = -INF.
• Với truy vấn loại 2, nếu \(l = r\) (đoạn độ dài < 2), ta in ngay ra -1.

2. Độ phức tạp

• Dựng cây (Build): O(N)
• Cập nhật điểm (Update): O(log N)
• Truy vấn đoạn (Query): O(log N)
• Tổng độ phức tạp thời gian: O((N + Q) log N).
• Không gian bộ nhớ: O(N) để lưu trữ Segment Tree.