P4400子集求和 | ||
|
Description
给你一个长度为n的整数序列A,其中的元素编号1到n。
同时给你m个集合S1,S2,......,Sm。每个集合里都是一些编号,这些编号对应的是A序列中的元素。你要进行q次操作,操作分两种:
1.查询第k个集合中编号对应A序列中的元素之和
2.把第k个集合中的编号对应A序列中的元素全部加上x
Input Format
第一行,三个整数n,m,q分别表示序列长度,集合数和操作数;
第二行,n个空格间隔的整数,依次表示A序列中编号1到n的元素A1,A2,...,An( |Ai|≤10^8));
接下来m行,每行描述一个集合:首先是一个整数T表示该集合的元素个数,然后是T个整数,表示对应A序列中的元素的编号;
接下来q行每行表示一个操作:
? k表示查询第k个集合中的数字对应A序列的元素之和
+ k x表示把第k个集合中对应A序列中的元素全部加上x
Output Format
对于每次询问,输出一行,一个整数,表示查询结果
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
Sample Input 2
10 10 10
0 0 0 1 -5 8 7 2 9 -2
8 1 9 7 8 2 5 10 3
2 7 10
8 8 7 1 4 2 5 10 9
2 7 5
8 9 3 6 4 8 1 2 10
2 9 2
8 4 2 9 1 10 7 5 3
2 3 6
8 2 8 5 9 4 1 6 10
2 5 2
? 1
? 3
? 5
? 4
+ 9 0
+ 2 -5
+ 4 7
+ 5 -1
? 2
? 7
Sample Output 2
11
12
18
2
1
8
Hint
1 ≤ k ≤ m, |x| ≤ 10^8
1 ≤ n, q ≤ 10^5
1 ≤ T≤ n
1≤ m ≤5000
数据保证,m个集合的元素个数总和不超过10^5
Source 改编自CodeForces 348C