Tin học trẻ 2021 TPHCM - Vòng Sơ Loại - Bảng C - ABCD

View as PDF

Submit solution

Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
Tin học trẻ 2021 TPHCM - Vòng Sơ Loại - Bảng C
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 \}~.

Comments

Please read the guidelines before commenting.



  • 0
    khongbiet   commented on 15, May, 2022, 14:20

    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 ạ ?


    • 0
      nmhienbn   commented on 15, May, 2022, 18:05

      Segment Tree nha bạn, Bạn có thể tham khảo https://oj.vnoi.info/problem/segtree_itladder


      • 0
        khongbiet   commented on 15, May, 2022, 21:24

        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