Олимпиадный тренинг

Задача . C. Суммы подмножеств


Задача

Темы: Перебор Структуры данных *2500

Дан массив a1, a2, ..., an и m множеств S1, S2, ..., Sm индексов элементов этого массива. Введем обозначение, Sk = {Sk, i} (1 ≤ i ≤ |Sk|), другими словами Sk, i — это некоторый элемент множества Sk.

В задаче нужно ответить на q запросов. Каждый запрос имеет один из следующих типов:

  1. Найти сумму элементов с индексами из множества Sk: . Формат запроса — «? k».
  2. Добавить число x ко всем элементам с индексами из множества Sk: aSk, i заменяется на aSk, i + x для всех i (1 ≤ i ≤ |Sk|). Формат запроса — «+ 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 
-3
4
9

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет