TLEoj Contest #07 - Tổng tích lũy
Xem PDF
Nộp bài
Điểm:
1500 (thành phần)
Thời gian:
1.0s
Python 3
3.0s
Bộ nhớ:
256M
Python 3
512M
Input:
bàn phím
Output:
màn hình
Tác giả:
Dạng bài
Tachi có một bài toán nho nhỏ và cần bạn giúp đỡ.
Anh ta có số nguyên N, Q và mảng A = (A_1,..., A_N).
Tachi cần xử lí Q truy vấn, mỗi truy vấn trong đó thuộc một trong hai loại sau đây:
1 x v: cập nhật A_x thành v.2 x: ta có B_i = \sum_{j = 1}^{i} A_j, C_i = \sum_{j = 1}^{i} B_j và D_i = \sum_{j = 1}^{i} C_j. In ra phần tử D_x chia dư cho 998244353.
Input, Output và Subtasks
Input: (bàn phím)
- Dòng đầu tiên chứa 2 số nguyên N và Q (1 \le N, Q \le 2 x 10^5).
- Dòng tiếp theo chứa N số nguyên: A_1, A_2,..., A_N (0 \le A_i \le 10^9).
- Q dòng tiếp theo, chứa truy vấn cần xử lí, dịnh dạng của truy vấn được miêu tả như đề trên (1 \le x \le N, 0 \le v \le 10^9).
Output: (màn hình)
- Khi gặp truy vấn loại 2 thì trả lời như đề đã đưa ra, khi trả lời thì xuống dòng.
Sample 1
Input (bàn phím)
3 3
1 2 3
2 3
1 2 0
2 3
Output (màn hình)
15
9
Notes
- Ở truy vấn thứ nhất, A = (1, 2, 3), vì vậy B = (1, 3, 6), C = (1, 4, 10), và D = (1, 5, 15). Do đó D_3 = 15.
- Ở truy vấn thứ 3, A = (1, 0, 3), vì vậy B = (1, 1, 4), C = (1, 2, 6), và D = (1, 3, 9). Do đó D_3 = 9.
Sample 1
Input (bàn phím)
2 1
998244353 998244353
2 1
Output (màn hình)
0
Bình luận