Tóm tắt đề

• Cho dãy số nguyên $A$ gồm $n$ phần tử ($A_1,A_2,...,A_n$) có giá trị ban đầu bằng 0.
• Cho $Q$ truy vấn dạng $(u,v,m)$ tăng giá trị các phần tử trong đoạn $[u,v]$ lên $M$.
• Sau $Q$ truy vấn, tìm số lớn nhất trong mảng $A$.

Giới hạn bài

• Subtask 1: Có 70% test: $1\le n,$ $Q\le {10}^3$
• Subtask 2: Có 30% test: ${10}^3<n$ $Q\le {10}^6$

Lời giải

Subtask 1: $1\le n,$ $Q\le {10}^3$

Tiếp cận

Trong $Q$ truy vấn sử dụng vòng for để tăng giá trị các phần tử trong đoạn $[u,v]$ lên $M$. Kết thúc truy vấn, tìm max trong mảng.

Thực hiện

Với mỗi truy vấn, sử dụng một vòng lặp từ $u$ đến $v$ để tăng giá trị phần tử lên $m$. Sau $Q$ truy vấn, tìm max trong mảng $A$.

Độ phức tạp

Subtask 2: ${10}^3<n,$ $Q\le {10}^6$

Tiếp cận

Với $n\times Q$ lớn, cần một cách khác tối ưu hơn để cập nhật giá trị của đoạn $[u,v]$. Đây là ứng dụng cơ bản của mảng hiệu. Gọi $f_i$ là hiệu của $A_i$ với $A_{i-1}$. Khi gặp truy vấn $(u,v,m)$ thì chỉ có hiệu của $A_u$ và $A_{u-1}$ hiệu của $A_v$ và $A_{v+1}$ thay đổi, cụ thể là $f_u$ tăng lên $m$ và $f_{v+1}$ giảm đi $m$. Kết thúc truy vấn, tìm max trong mảng.

Thực hiện

Với mỗi truy vấn, tăng $f_u$ lên $m$ và giảm $f_{v+1}$ đi $m$. Sau đó, cộng dồn mảng diff để tìm được từng $A_i$, tìm max.

Độ phức tạp

$O(n)$.