Subset Sums

题意翻译

给定一个n个数的序列a,m个下标集合,记 $S_{k}=\{S_{k,i}\}$。 两种操作: $1. $? k 求集合k的和,即 求集合k 所有元素做原数组下标的和 $2.$ + k w 给集合k的所有下标代表的数加w。 ## 输入输出格式 ### 输入格式 输入的第一行包括三个整数 $n$ , $m$ 和 $q$ $( 1<=n, m, q<=10^5 )$ 。第二行包括n个整数 $ a_1, a_2, ..., a_n $ , 表示数组 $a$ 。 接下来的 $m$ 行,每行描述了一个集合。第 $k$ 行首先包括一个正整数 $x$ ,表示集合 $S_k$ 的大小。接下来是 $x$ 个正整数,表示集合 $S_k$ 的元素所处的下标。 接下来的 $q$ 行是将要进行的操作。每种操作占一行。第一种操作形如 `? k` ,表示询问集合 $S_k$ 中所有元素的和。第二种操作形如 `+ k x`, 表示将集合 $S_k$ 中的所有元素加上 $x$ 。对于每个询问,都有 $( 1<=k<=m, |x|<=10^8 )$ 。 保证所有集合的元素数量和不超过 $10^5$ 。 ### 输出格式 对于每个 `? k` 操作,请输出集合 $S_k$ 的元素之和。 注意:因为评测机的平台原因,请使用 `cin` `cout` 或 `%l64d` 输入输出64位整数。 感谢@elijahqi @星烁晶熠辉 提供的翻译

题目描述

You are given an array $ a_{1},a_{2},...,a_{n} $ and $ m $ sets $ S_{1},S_{2},...,S_{m} $ of indices of elements of this array. Let's denote $ S_{k}={S_{k,i}} (1<=i<=|S_{k}|) $ . In other words, $ S_{k,i} $ is some element from set $ S_{k} $ . In this problem you have to answer $ q $ queries of the two types: 1. Find the sum of elements with indices from set $ S_{k} $ : ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF348C/b362cd2153c6c0b48250fc2b666a4c233257f4d7.png). The query format is "? k". 2. Add number $ x $ to all elements at indices from set $ S_{k} $ : $ a_{Sk,i} $ is replaced by $ a_{Sk,i}+x $ for all $ i $ $ (1<=i<=|S_{k}|) $ . The query format is "+ k x". After each first type query print the required sum.

输入输出格式

输入格式


The first line contains integers $ n,m,q $ $ (1<=n,m,q<=10^{5}) $ . The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ $ (|a_{i}|<=10^{8}) $ — elements of array $ a $ . Each of the following $ m $ lines describes one set of indices. The $ k $ -th line first contains a positive integer, representing the number of elements in set ( $ |S_{k}| $ ), then follow $ |S_{k}| $ distinct integers $ S_{k,1},S_{k,2},...,S_{k,|Sk}| $ $ (1<=S_{k,i}<=n) $ — elements of set $ S_{k} $ . The next $ q $ lines contain queries. Each query looks like either "? k" or "+ k x" and sits on a single line. For all queries the following limits are held: $ 1<=k<=m $ , $ |x|<=10^{8} $ . The queries are given in order they need to be answered. It is guaranteed that the sum of sizes of all sets $ S_{k} $ doesn't exceed $ 10^{5} $ .

输出格式


After each first type query print the required sum on a single line. Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #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

输出样例 #1

-3
4
9