読者です 読者をやめる 読者になる 読者になる

今日の典型データ構造②

今日の典型データ構造です。

N個のpairが与えられます ただしstringの長さは合計して10^6以下です

Q個の以下のクエリが与えられる

  • k(int), x(int) が与えられる k番目のデータのintを+xする
  • s(string) が与えられる s をprefixに持つ文字列を持つデータのintのsumを求める

ただし2種類目のクエリで与えられる文字列の長さのsumは10^6以下

例えば最初のデータが
{kita, 100}
{yuta, 10}
{kitakita, -100}
{yutaka1999, 30}
として、

2種類目のクエリでs=yuが飛んできたら答えは10+30=40
2種類目のクエリでs=kitayutaが飛んできたら答えは0
1種類目のクエリでk=3, x=-100が飛んできたらデータは

{kita, 100}
{yuta, 10}
{kitakita, -200}
{yutaka1999, 30}

ここで2種類目のクエリでs=kitaが飛んできたら答えは100+(-200)=-100


N = Q = 10^5 TLE3s