Range Queries and Copies
Xem PDF
Điểm:
350 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho một tập các mảng mà ban đầu chỉ có một mảng. Nhiệm vụ của bạn là thực hiện các truy vấn sau:
- \(1\) \(k\) \(a\) \(x\): Thay đổi phần tử thứ \(a\) ở mảng thứ \(k\) thành \(x\).
- \(2\) \(k\) \(a\) \(b\): Tính tổng các phần tử trong đoạn \([a, b]\) ở mảng \(k\).
- \(3\) \(k\): Tạo một bản sao của mảng \(k\) và đưa vào cuối tập các mảng.
Input
- Dòng thứ nhất gồm hai số nguyên dương \(N, Q\): kích thước từng mảng và số truy vấn.
- Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((1 \leq A_i \leq 10^9)\).
- \(Q\) dòng tiếp theo, mỗi dòng là một truy vấn thuộc một trong ba dạng sau:
- \(1\) \(k\) \(a\) \(b\) \((1 \leq k \leq\) số mảng hiện tại, \(1 \leq a \leq b \leq N)\).
- \(2\) \(k\) \(a\) \(b\) \((1 \leq k \leq\) số mảng hiện tại, \(1 \leq a \leq b \leq N)\).
- \(3\) \(k\) (\(1 \leq k \leq\) số mảng hiện tại).
Output
- In ra kết quả cho các truy vấn \(2\).
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 2.10^3\).
- Subtask \(2\) (\(50\%\) số điểm) \(N, Q \leq 2.10^5\).-
Example
Test 1
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
Bình luận
xin cái giải thích ví dụ :v
🙂 hiểu rồi, xét N mảng
Tối đa Q+1 mảng, mỗi mảng luôn có N phần tử
hack test 🙂