CSES - Range Queries and Copies | Truy vấn đoạn và bản sao
Xem PDF
Điểm:
2000 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Nhiệm vụ của bạn là duy trì một danh sách các mảng, danh sách ban đầu chỉ có một mảng duy nhất. Bạn phải xử lý các loại truy vấn sau:
- Gán giá trị \(a\) trong mảng \(k\) thành \(x\).
- Tính tổng các giá trị trong đoạn \([a,b]\) trong mảng \(k\).
- Tạo một bản sao của mảng \(k\) và thêm nó vào cuối danh sách.
Input
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\): kích thước của mảng và số lượng truy vấn.
- Dòng tiếp theo chứa \(n\) số nguyên \(t_1, t_2, \dots, t_n\): các giá trị ban đầu của mảng.
- \(q\) dòng cuối cùng mô tả các truy vấn. Định dạng của từng truy vấn là một trong các kiểu sau:
1 k a x,2 k a bor3 k.
Output
- In ra kết quả của từng truy vấn tính tổng.
Constraints
- \(1 \le n, q \le 2 \times 10^5\)
- \(1 \le t_i, x \le 10^9\)
- \(1 \le a \le b \le n\)
Example
Sample 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
Sample output
13
13
13
15
Bình luận
Cho em hỏi mảng k ở thao tác 3 nghĩa là gì ạ
thao tác 3 là thêm copy của mảng thứ k trong danh sách các mảng vào cuối danh sách nhé bạn