今日の典型データ構造です。
N個のpair
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