Truy vấn tổng cấp số cộng

Xem PDF

Điểm: 650 Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho dãy \(a_{1}, a_{2}, \ldots, a_{n}\) gồm các số tự nhiên. Cần thực hiện \(q\) truy vấn, mỗi truy vấn là một trong hai thao tác sau:

  1. Nhập vào hai số nguyên \(i, u\) \((1 \leq i \leq n, 0 \leq u \leq 10^{9})\). Cập nhật \(a_{i} = u\).
  2. Nhập vào hai số nguyên \(p, k\) \((1 \leq p, k \leq n)\). Hãy tính tổng \(a_{p} + a_{p + k} + a_{p + 2k} + \ldots + a_{p + uk}\) với u là số nguyên lớn nhất sao cho \(p + uk \leq n\).

Input

  • Dòng đầu tiên chứa một số nguyên dương \(n\) \((n \leq 2 \times 10^{5})\).
  • Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((0 \leq a_{i} \leq 10^{9})\).
  • Dòng thứ ba chứa một số nguyên dương \(q\) \((q \leq 2 \times 10^{5})\), số lượng truy vấn.
  • \(q\) dòng tiếp theo, mỗi dòng có một trong hai dạng sau:
    • \(1\) \(i\) \(u\): cập nhật \(a_{i} = u\).
    • \(2\) \(p\) \(k\): in ra tổng \(a_{p} + a_{p + k} + a_{p + 2k} + \ldots\).

Output

  • Với mỗi truy vấn 2, in ra đáp số trên một dòng.

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 2000\).
  • Subtask \(2\) (\(40\%\) số điểm): đều là loại 2 (không có truy vấn cập nhật).
  • Subtask \(3\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

Test 1

Input
8
6 7 1 3 9 0 7 5
5
2 1 1
2 3 2
1 5 3
2 1 1
2 3 2
Output
38
17
32
11
Note
  • Trong truy vấn 1, ta cần in ra \(a_{1} + a_{2} + ... + a_{8} = 38\).
  • Trong truy vấn 2, ta cần in ra \(a_{3} + a_{5} + a_{7} = 1 + 9 + 7 = 17\).
  • Trong truy vấn 3, ta cập nhật \(a_{5} = 3\).

Bình luận


  • -5
    BETTER 9:15 p.m. 1 Tháng 5, 2021

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.