Subset Sums
View as PDFBạn được cho một dãy số ~A_1~, ~A_2~, ..., ~A_n~ và ~m~ tập hợp ~S_1~, ~S_2~, ..., ~S_m~ các chỉ số của mảng này. Gọi ~S_k = \{S_{k, i}\}, 1 \leq i \leq |S_k|~. Nói cách khác, ~S_{k, i}~ là một phần tử bất kỳ từ tập hợp ~S_k~.
Trong bài này bạn sẽ phải trả lời ~q~ truy vấn có 2 dạng sau:
~?\ k~: Tính tổng ~\displaystyle \sum^{|S_k|}_{i = 1}{A_{S_{k, i}}}~, hay tổng các phần tử có vị trí thuộc tập ~S_k~ của dãy ~A~.
~+\ k\ x~: Cộng ~x~ vào các phần tử của dãy ~A~ có chỉ số trong tập ~S_k~. Phần tử ~A_{S_{k, i}}~ được thay bằng ~A_{S_{k, i}} + x~ với mọi ~i \in [1, |S_k|]~.
Với mỗi truy vấn loại đầu tiên hãy in tổng đã tính.
Input
Dòng đầu tiên gồm 3 số ~n, m, q~ (~1 \leq n, m, q \leq 10^5~). Dòng thứ hai gồm ~n~ phần tử ~A_1, A_2, \cdots, A_n~ (~|A_i| \leq 10^8~), các phần tử của dãy ~A~.
~m~ dòng tiếp theo, dòng thứ ~k~ gồm một số nguyên dương ở đầu cho biết số lượng phần tử của tập ~S_k~, theo sau bởi ~|S_k|~ số nguyên dương phân biệt ~S_{k, 1}, S_{k, 2}, \cdots, S_{k, |S_k|}~ (~1 \leq S_{k, i} \leq n~).
~q~ dòng tiếp theo, mỗi dòng có dạng ~?\ k~ hoặc ~+\ k\ x~. Với mọi truy vấn có ~1 \leq k \leq m~, ~|x| \leq 10^8~. Các truy vấn được cho theo thứ tự chúng cần được trả lời.
Đề đảm bảo tổng của kích thước mọi tập ~S_k~ không quá ~10^5~.
Output
Sau mỗi truy vấn dạng đầu tiên hãy in tổng đã tính trên một dòng.
Sample Input 1
5 3 5
5 -5 5 1 -4
2 1 2
4 2 1 4 5
2 2 5
? 2
+ 3 4
? 1
+ 2 1
? 2
Sample Output 1
-3
4
9
Notes
Ở truy vấn đầu tiên, tập ~S_k~ là ~S_2~ có 4 phần tử ~\{2, 1, 4, 5\}~. Tổng của 4 phần tử có vị trí trong tập ~S_2~ là ~A_2 + A_1 + A_4 + A_5 = -5 + 5 + 1 + (-4) = -3~.
Comments
https://codeforces.com/problemset/problem/348/C
This comment is hidden due to too much negative feedback. Show it anyway.