← 返回题目列表

Codeforces · 348/C

C. 子集和

中文机器翻译题面 查看原题

给定一个数组 a1, a2, ..., an 和 m 集合 S1, S2, ..., Sm 该数组元素的索引。让我们表示 Sk = {Sk, i} (1 ≤ i ≤ |Sk|)。换句话说,Sk, i 是集合 Sk 中的某个元素。

在这个问题中,你必须回答两种类型的q个查询:

1. 求集合 Sk 中具有索引的元素之和:$$\frac{|S_k|}{\sum_{i=1}^{n} a_{S_k,i}}$$。查询格式为“?k”。
2. 将数字 x 添加到集合 Sk 中索引处的所有元素:aSk, i 被 aSk 替换,对于所有 i (1 ≤ i ≤ |Sk|), i + x。查询格式为“+k x”。

在每个第一种类型的查询之后打印所需的总和。

输入

第一行包含整数 n、m、q (1 ≤ n、m、q ≤ 105)。第二行包含 n 个整数 a1, a2, ..., an (|ai| ≤ 108) — 数组 a 的元素。

以下 m 行中的每一行描述一组索引。第k行首先包含一个正整数,表示集合(|Sk|)中元素的数量,然后是|Sk|不同的整数 Sk, 1, Sk, 2, ..., Sk, |Sk| (1 ≤ Sk, i ≤ n) — 集合 Sk 的元素。

接下来的 q 行包含查询。每个查询看起来像“? k”或“+ k x”并且位于一行上。对于所有查询,都保持以下限制:1 ≤ k ≤ m,|x| ≤ 108。问题按照需要回答的顺序给出。

保证所有集合Sk的大小之和不超过105。

输出

在每个第一种类型的查询之后,在一行上打印所需的总和。

请不要编写 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

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