区間総和が X step.2 Rust(Beta)編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
(問題)
長さ n の配列 A が与えられます。Q 個のクエリが与えられるので順番に処理してください。i (1 ≦ i ≦ Q) 番目のクエリは以下の通りです。
Yes を、そうでないなら No を出力する。(ヒント):問題 9 での解法を BIT を使って、更新処理を含めても高速に処理できるようにしましょう。
- 入力される値
-
入力は以下のフォーマットで与えられます。
n
A_1 A_2 ... A_n
Q
q_1 p_1 X_1
q_2 p_2 X_2
...
q_Q p_Q X_Q- 1 行目には 1 つの整数 n が与えられます。
- 2 行目には n 個の整数 A_1, A_2, ..., A_n が与えられます。
- 3 行目には 1 つの整数 Q が与えられます。
- 3 + i (1 ≦ i ≦ Q) 行目には 3 つの整数 q_i, p_i, X_i が与えられます。
- 入力は合計 3 + Q 行からなり、入力値最終行の末尾に改行を 1 つ含みます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
q_i = 2 となる i の個数を T としたとき答えを T 行で出力してください。
j (1 ≦ j ≦ T) 行目には、q_i = 2 となるクエリの中で前から j 番目のクエリの答えを出力してください。
- 条件
-
すべてのテストケースについて以下の条件を満たします。
- 1 ≦ n ≦ 25000
- 1 ≦ A_i ≦ 10 ^ 9 (1 ≦ i ≦ n)
- 1 ≦ Q ≦ 25000
- 1 ≦ q_i ≦ 2 (1 ≦ i ≦ Q)
- 1 ≦ p_i ≦ n (1 ≦ i ≦ Q)
- q_i = 1 のとき 1 ≦ X_i ≦ 10 ^ 9 (1 ≦ i ≦ Q)
- q_i = 2 のとき 1 ≦ X_i ≦ 10 ^ 15 (1 ≦ i ≦ Q)
- 入力例1
-
10
2 7 1 8 2 8 1 8 2 8
8
2 5 10
2 10 10
1 6 2
2 6 17
2 6 18
2 6 19
1 10 10
2 9 20
- 出力例1
-
Yes
No
No
No
Yes
Yes
