Prefix Sum Query (累積和クエリ)
正の整数が並ぶ配列
n個が与えられています。あなたのタスクは、この配列に対してq回のクエリを処理することです。クエリには次の2種類があります:- 配列の先頭から始まる部分配列（いわゆるプレフィックス）の合計値が、与えられた数値
sに等しいものが存在するかどうかを確認する。
- 配列の特定のインデックスにある値を更新する。
これらのクエリに効率的に答えるプログラムを作成してください。
入力
最初の行には、配列の大きさを表す
nとクエリの数を表すqが、スペース区切りで与えられます (1 ≤ n, q ≤ 100 000)。次の行には、配列の要素である
n個の正の整数が与えられます。各要素は正であり、を超えません。続く
q行にわたってクエリの内容が与えられます。各クエリはクエリの種類を示す（1または2）と、その種類に応じた引数を含みます。- クエリタイプ1の場合: 整数
sが与えられます。
- クエリタイプ2の場合: 配列の位置
pと、そこに代入する値xが与えられます。
出力
クエリタイプ1に対しては、条件を満たすプレフィックスが存在するなら
YES、存在しないなら NO を出力してください。例
入力 | 出力 |
5 3
1 2 3 4 5
1 10
2 2 3
1 15 | YES
NO |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB