Truy vấn đoạn và bản sao (Range Queries and Copies)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Ban đầu có đúng một mảng độ dài $n$. Cần duy trì một danh sách các mảng và xử lý ba loại thao tác: 1 k a x gán phần tử $a$ của mảng $k$ bằng $x$; 2 k a b hỏi tổng đoạn $[a,b]$ của mảng $k$; 3 k tạo một bản sao độc lập của mảng $k$ và thêm vào cuối danh sách.

Dữ liệu vào

Dòng đầu chứa $n,q$. Dòng thứ hai chứa mảng ban đầu. Tiếp theo là $q$ thao tác ở một trong ba dạng trên.

Kết quả

Với mỗi thao tác loại 2, in tổng đoạn trên một dòng.

Subtask

Subtask 1 (20%)

• $n\le 30$, số truy vấn $\le 30$.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, số truy vấn $\le 3000$.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le2\cdot10^5$
• $1\le t_i,x\le10^9$
• $1\le a\le b\le n$
• mọi chỉ số phiên bản $k$ luôn chỉ tới một mảng đã tồn tại

Ví dụ

Input

5 6
2 3 1 2 5
3 1
2 1 1 5
2 2 1 5
1 2 2 5
2 1 1 5
2 2 1 5

Output

13
13
13
15

Giải thích

Sau 3 1, mảng số 2 là bản sao của mảng 1. Cập nhật 1 2 2 5 chỉ thay đổi mảng 2; vì vậy tổng toàn mảng 1 vẫn là $13$ còn mảng 2 trở thành $15$.