Cập nhật đoạn và truy vấn tổng

Arrays Buổi 15 — Prefix Sum & Difference Array prefix-sum
Points
18
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Cho mảng số nguyên $A$ gồm $N$ phần tử. Ban đầu thực hiện $M$ phép cập nhật: mỗi phép cộng $V$ vào mọi phần tử từ $L$ đến $R$. Sau khi hoàn thành tất cả $M$ phép cập nhật, hãy trả lời $Q$ truy vấn tính tổng các phần tử từ vị trí $L$ đến $R$.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $N, M, Q$. Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$. $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $L, R, V$. $Q$ dòng cuối cùng, mỗi dòng chứa hai số nguyên $L, R$.

Dữ liệu ra

Với mỗi truy vấn, in ra tổng đoạn tương ứng trên một dòng.

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

$1 \le N, Q \le 10^5$, $0 \le M \le 10^5$, $|A_i|, |V| \le 10^9$.

Draft saved