Nhật ký năng lượng sau hiệu chỉnh

Bối cảnh và bài toán

Một hệ thống giám sát lưu mức tiêu thụ năng lượng theo từng phút. Sau khi đối soát, kỹ sư nhận được một loạt hiệu chỉnh: mỗi hiệu chỉnh cộng cùng một lượng vào toàn bộ một đoạn thời gian. Tất cả hiệu chỉnh được áp dụng trước khi bộ phận phân tích gửi các truy vấn tổng trên những khoảng thời gian khác nhau.

Dữ liệu có thể rất lớn, vì vậy cập nhật từng phần tử cho từng hiệu chỉnh rồi lại cộng từng đoạn cho từng truy vấn sẽ lặp lại quá nhiều công việc.

Yêu cầu

Áp dụng toàn bộ các hiệu chỉnh theo đoạn, sau đó trả lời tổng giá trị trên từng đoạn truy vấn.

Input

• Dòng 1: n u q — số phần tử, số hiệu chỉnh và số truy vấn.
• Dòng 2: n số nguyên a[i].
• u dòng tiếp theo: l r delta, cộng delta vào mọi a[i] với l <= i <= r.
• q dòng cuối: l r, yêu cầu tổng của mảng sau hiệu chỉnh trên đoạn [l,r].

Output

Với mỗi truy vấn, in một dòng chứa tổng trên đoạn tương ứng sau khi tất cả hiệu chỉnh đã được áp dụng.

Ràng buộc

• 1 <= n, q <= 2 * 10^5
• 0 <= u <= 2 * 10^5
• |a[i]| <= 10^9
• |delta| <= 10^9
• 1 <= l <= r <= n

Chấm điểm

Ví dụ 1

Input

5 2 3
1 2 3 4 5
1 3 2
2 5 -1
1 5
2 4
3 3

Output

17
10
4

Giải thích. Sau hai hiệu chỉnh, mảng trở thành [3,3,4,3,4]. Tổng các đoạn [1,5], [2,4], [3,3] lần lượt là 17, 10, 4.

Ví dụ 2

Input

4 1 2
10 20 30 40
2 4 5
1 2
3 4

Output

35
80

Giải thích. Mảng cuối là [10,25,35,45]; do đó hai tổng cần in là 35 và 80.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.