Tóm tắt đề bài

Có ~n~ khu vực trên một đường thẳng. Có ~q~ camera tại vị trí ~c_1, c_2, ..., c_q~. Mỗi camera ~c_i~ giám sát từ ~c_i - r~ đến ~c_i + r~. Tính số lượng camera giám sát trong khu vực từ ~1~ đến ~n~.

Giới hạn: ~1 \le n \le 10^5~, ~1 \le q \le 10^5, 0 \le r < n, 1 \le c_i \le n~

Subtask 1: ~r = 0~

Mỗi camera chỉ có thể giám sát tại vị trí của chính nó. Đáp số chính là số camera từng vị trí.

ĐPT: ~O~(~n + q~)

Subtask 2: ~n, q \le 7000~

Với giới hạn này, ta hoàn toàn có thể mô phỏng lại tất cả các vị trí mà từng camera giám sát trên mảng.

ĐPT: ~O~(~q \times r~)

Subtask 3 + 4: Không có giới hạn gì thêm

Đây là subtask tối ưu từ subtask 2.

Ta sẽ sử dụng mảng hiệu (difference array) để có thể cập nhật hàng loạt các đầu mút mà từng camera giám sát. Sau đó, ta sẽ sử dụng mảng cộng dồn để có thể mô phỏng lại số lượng camera của từng vị trí ~i~ với ~1 \le i \le n~.

ĐPT: ~O~(~q + n~)