Duy trì danh sách mảng và xử lý truy vấn

Xem dạng PDF

Mô tả bài toán: Duy trì danh sách mảng và xử lý truy vấn

Bạn có một danh sách các mảng, ban đầu chỉ có một mảng duy nhất. Nhiệm vụ của bạn là xử lý các truy vấn thuộc các loại sau:

  1. Gán giá trị: Gán giá trị x cho phần tử thứ a trong mảng thứ k.
  2. Tính tổng đoạn: Tính tổng các giá trị trong đoạn [a,b] của mảng thứ k.
  3. Tạo bản sao: Tạo một bản sao của mảng thứ k và thêm nó vào cuối danh sách các mảng.

Input:

  • Dòng đầu tiên chứa hai số nguyên nq: kích thước mảng và số lượng truy vấn.
  • Dòng tiếp theo chứa n số nguyên t1,t2,...,tn: nội dung ban đầu của mảng.
  • Sau đó có q dòng, mỗi dòng mô tả một truy vấn:
    • 1 k a x: Gán giá trị x cho phần tử thứ a trong mảng thứ k.
    • 2 k a b: Tính tổng các giá trị trong đoạn [a,b] của mảng thứ k.
    • 3 k: Tạo một bản sao của mảng thứ k và thêm nó vào cuối danh sách các mảng.

Output:

  • Với mỗi truy vấn loại 2, in ra tổng của đoạn được yêu cầu.

Constraints:

  • 1n,q2105
  • 1ti,x109
  • 1k số mảng hiện tại.
  • 1abn

Ví dụ:

Input:
Copy
5 6
2 3 1 2 5
3 1
2 1 1 5
2 2 1 5
1 2 2 5
2 1 2 5
2 2 1 5
Output:
Copy
13
13
13
15

Giải thích ví dụ:

  1. Mảng ban đầu: [2, 3, 1, 2, 5].

  2. Truy vấn 3 1: Tạo một bản sao của mảng thứ 1 (ban đầu) và thêm nó vào danh sách:

    • Danh sách các mảng: [[2, 3, 1, 2, 5], [2, 3, 1, 2, 5]].
  3. Truy vấn 2 1 1 5: Tính tổng đoạn [1,5] của mảng thứ 1:

    • Tổng: 2+3+1+2+5=13.
    • Kết quả là 13.
  4. Truy vấn 2 2 1 5: Tính tổng đoạn [1,5] của mảng thứ 2:

    • Tổng: 2+3+1+2+5=13.
    • Kết quả là 13.
  5. Truy vấn 1 2 2 5: Gán giá trị 5 cho phần tử thứ 2 trong mảng thứ 2:

    • Mảng thứ 2: [2, 5, 1, 2, 5].
    • Danh sách các mảng: [[2, 3, 1, 2, 5], [2, 5, 1, 2, 5]].
  6. Truy vấn 2 1 2 5: Tính tổng đoạn [2,5] của mảng thứ 1:

    • Tổng: 3+1+2+5=13.
    • Kết quả là 13.
  7. Truy vấn 2 2 1 5: Tính tổng đoạn [1,5] của mảng thứ 2:

    • Tổng: 2+5+1+2+5=15.
    • Kết quả là 15.



Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.

Gửi bài giải
Điểm: 10,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Nguồn bài: CSES
Dạng bài
CSES
Ngôn ngữ cho phép
C
C++
Java
Kotlin
Pascal
PyPy
Python
Scratch