Cộng đoạn trên phiên bản và tổng đoạn

Buổi 30 — Persistent Segment Tree
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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.
Draft saved