Cộng đoạn trên phiên bản và tổng đoạn
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho mảng $a_1,\dots,a_n$ là phiên bản $0$. Xử lý $q$ thao tác (mỗi thao tác loại $1$ tạo phiên bản mới có số hiệu tiếp theo):
1 v l r x: tạo phiên bản mới từ phiên bản $v$ bằng cách cộng $x$ vào mọi $a_i$ với $l\le i\le r$.2 v l r: in tổng $a_l+\dots+a_r$ của phiên bản $v$.
Dữ liệu vào
Dòng đầu: $n,q$. Dòng hai: $n$ số nguyên. Sau đó $q$ dòng thao tác. Phiên bản $v$ luôn tồn tại.
Dữ liệu ra
Với mỗi thao tác loại $2$ in một dòng là tổng.
Ví dụ
Input
5 5
-1 5 1 2 -7
2 0 1 1
2 0 5 5
2 0 1 5
1 0 1 5 8109
1 0 3 4 -348
Output
-1
-7
0
Giới hạn
- $1\le n\le 10^5$; $1\le q\le 5\cdot 10^4$; $|a_i|\le 10^9$; $|x|\le 10^4$.
- Thời gian: 2 giây; bộ nhớ: 256 MB.
Community Discussion