TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P4400
  • 問題
  • P4400子集求和
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 时间限制1s,空间限制256m
    問題説明

    给你一个长度为n的整数序列A,其中的元素编号1到n。
    同时给你m个集合S1,S2,......,Sm。每个集合里都是一些编号,这些编号对应的是A序列中的元素。你要进行q次操作,操作分两种:
    1.查询第k个集合中编号对应A序列中的元素之和
    2.把第k个集合中的编号对应A序列中的元素全部加上x

    入力形式

    第一行,三个整数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

    出力形式

    对于每次询问,输出一行,一个整数,表示查询结果

    サンプル入力 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

    サンプル入力 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

    サンプル出力 2

    11
    12
    18
    2
    1
    8

    ヒント

    1 ≤ k ≤ m, |x| ≤ 10^8
    1 ≤ n, q ≤ 10^5
    1 ≤ T≤ n
    1≤ m ≤5000
    数据保证,m个集合的元素个数总和不超过10^5


    ソース  改编自CodeForces 348C