Cập nhật đoạn và truy vấn tổng
Points
18
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Đề 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$.
Community Discussion