Phiên bản mảng và tổng đoạn
Points
10
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho mảng $a_1,\dots,a_n$ (phiên bản $0$). Bạn cần xử lý $q$ thao tác; mỗi thao tác loại $1$ tạo ra phiên bản mới có số hiệu bằng số phiên bản hiện có (lần lượt $1,2,\dots$).
1 v i x: tạo phiên bản mới từ phiên bản $v$ bằng cách cộng $x$ vào $a_i$.2 v l r: in ra 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 $a_i$. Tiếp theo $q$ dòng là các 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à đáp án.
Ví dụ
Input
5 5
7 -1 9 -10 9
2 0 1 4
2 0 4 4
1 0 2 951067984
2 1 3 5
1 1 5 443043973
Output
5
-10
8
Giới hạn
- $1\le n,q\le 10^5$; $|a_i|,|x|\le 10^9$; $1\le l\le r\le n$.
- Thời gian: 2 giây; bộ nhớ: 256 MB.
Community Discussion