Tin học trẻ 2021 TPHCM - Vòng Sơ Loại - Bảng C - ABCD
Xem dạng PDF
Cho dãy ~A~ gồm ~n~ số nguyên không âm, đánh số từ ~1~. Dãy tổng tiền tố ~B~ của ~A~ được định nghĩa như sau: $$\begin{cases} B_i = & & A_1, & i = 1 \\ B_i = B_{i - 1} & + & A_i, & 1 < i \le n \end{cases}$$
Tương tự, ta định nghĩa ~C~ là dãy tổng tiền tố của ~B~, và ~D~ là dãy tổng tiền tố của ~C~.
Cho ~q~ truy vấn, mỗi truy vấn thuộc một trong hai dạng:
- ~U~ ~x~ ~y~: gán ~A_x = y~.
- ~T~ ~w~: cho biết giá trị của ~T_w~, nói cách khác, phần tử thứ ~w~ của mảng ~T~.
trong đó:
~x~ và ~w~ là các chỉ số hợp lệ ~(1 \le x, w \le n)~.
~T~ là một trong ~3~ kí tự ~\{ B, C, D \}~, hay ~T \in \{ B, C, D \}~.
Yêu cầu:
Hãy viết chương trình thực hiện các truy vấn và trả lời các truy vấn hỏi giá trị.
Dữ liệu:
Nhập từ bàn phím gồm:
- Dòng đầu chứa một số nguyên ~n~ ~(1 \le n \le 4 \times 10^5)~, là số phần tử của dãy ~A~.
- Dòng tiếp theo chứa ~n~ số nguyên cách nhau bởi khoảng trắng là các phần tử của dãy ~A~.
- Dòng đầu chứa một số nguyên ~q~ ~(1 \le q \le 4 \times 10^5)~, là số truy vấn bạn cần xử lý.
- ~q~ dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai dạng đã nêu.
Các tham số của mỗi truy vấn cách nhau bởi một khoảng trắng.
Kết quả:
In ra màn hình một dòng cho mỗi truy vấn cho mỗi truy vấn loại ~2~. Vì kết quả có thể rất lớn, bạn cần đưa ra phần dư của kết quả khi chia cho ~10^9 + 7~.
Sample Input:
4
1 7 0 9
5
B 3
C 2
D 4
U 2 5
D 4
Sample Output:
8
9
61
49
Giải thích:
Trước truy vấn thứ ~4~, ta có các dãy ~A, B, C, D~ như sau:
| A | 1 | 7 | 0 | 9 |
|---|---|---|---|---|
| B | 1 | 8 | 8 | 17 |
| C | 1 | 9 | 17 | 34 |
| D | 1 | 10 | 27 | 61 |
Ràng buộc:
- Tại mọi thời điểm, các phần tử của ~A~ có giá trị không vượt quá ~10^9~.
- ~20\%~ số điểm của bài tương ứng với các test có ~T \in \{ B \}~.
- ~30\%~ số điểm khác của bài tương ứng với các test có ~T \in \{ B, C \}~.
Bình luận
time ket si
Mọi người cho e hỏi, để giải quyết dc bài này có cần phải biết 1 số thuật toán hoặc cấu trúc dữ liệu gì đặc biệt ko ạ ?
Segment Tree nha bạn, Bạn có thể tham khảo https://oj.vnoi.info/problem/segtree_itladder
Cảm ơn b, bài itladder mình làm rồi, bài này mình cũng đùng segment tree nhưng có vẻ ko ổn lắm, mới dùng 2 mảng seg cho B,C là đã tle rồi
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Biết đâu bài bạn bị cả WA nữa ấy, vì bài này bạn không thấy kết quả cho từng test