Range Queries and Copies

Xem PDF



Tác giả:
Dạng bài
Đ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


  • 0
    vinhntndu    6:30 p.m. 3 Tháng 9, 2020

    xin cái giải thích ví dụ :v


    • 0
      hhoangcpascal    6:53 p.m. 3 Tháng 9, 2020 đã chỉnh sửa
      • 3 1: Tạo một mảng mới là mảng copy của mảng 1 (mảng ban đầu), đánh số mảng đó là số 2.
      • 2 1 1 5: Tính tổng mảng đầu tiên từ 1 tới 5: 2 + 3 + 1 + 2 + 5 = 13
      • 2 2 1 5: Tính tổng mảng thứ hai từ 1 tới 5: 2 + 3 + 1 + 2 + 5 = 13
      • 1 2 2 5: Thay đổi phần tử thứ 2 ở mảng thứ 2 (2, 3, 1, 2, 5) => (2, 5, 1, 2, 5).
      • 2 1 1 5: Tính tổng mảng đầu tiên từ 1 tới 5: 2 + 3 + 1 + 2 + 5 = 13
      • 2 2 1 5: Tính tổng mảng thứ hai từ 1 tới 5: 2 + 5 + 1 + 2 + 5 = 15

      • 0
        vinhntndu    6:55 p.m. 3 Tháng 9, 2020

        🙂 hiểu rồi, xét N mảng


        • 0
          hhoangcpascal    7:16 p.m. 3 Tháng 9, 2020 đã chỉnh sửa

          Tối đa Q+1 mảng, mỗi mảng luôn có N phần tử


          • 0
            vinhntndu    7:25 p.m. 3 Tháng 9, 2020

            hack test 🙂