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\le10^{3}$
• Subtask 2: Có 30% test: $10^{3}<n$ $Q\le10^{6}$</li>

Lời giải

Subtask 1: $1\le n,$ $Q\le10^{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

$O(n\times q).$

Subtask 2: $10^{3}<n,$ $Q\le10^{6}$</h5>

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)$.