(問題 12)ランプの切り替え part.2 C++編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
(問題)
ランプが N 個あり、左からランプ 1,ランプ 2, ..., ランプ N と並んでいます。始め M 個のランプ ランプ A_1, ランプ A_2, ランプ A_3, ..., ランプ A_M が赤色に光っており、その他は青色に光っています。Q 個のクエリが渡されるので、それぞれのクエリを処理してください。i 番目のクエリは以下の通りです。
(ヒント) 配列で管理することを考えましょう。ランプ i がどちらに光っているかを配列の i 番目で管理します。赤色に光っているとき 1 にして、青色に光っているとき適切な値で管理することで赤色に光っているランプの数を区間総和で計算することが出来ます。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N M
A_1 A_2 ... A_M
Q
q_1 I_1
q_2 I_2
...
q_Q I_Q
1 行目には 2 つの整数 N,M が与えられます。
2 行目には M 個の整数 A_1,A_2,...,A_M が与えられます。
3 行目には 1 つの整数 Q が与えられます。
3 + i (1 ≦ i ≦ Q) 行目には 2 つの整数 q_i,I_i が与えられます。
入力は合計 3 + Q 行からなり、入力値最終行の末尾に改行を 1 つ含みます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
q_i = 2 となる i の個数を q としたとき答えを q 行で出力してください。
j (1 ≦ j ≦ q) 行目には q_i = 2 となるクエリの中で j 番目のクエリの答えを出力してください。
- 条件
-
すべてのテストケースについて以下の条件を満たします。
- 1 ≦ M ≦ N ≦ 100000
- 1 ≦ A_i ≦ N (1 ≦ i ≦ M)
- i ≠ j なら A_i ≠ A_j
- 1 ≦ Q ≦ 100000
- 1 ≦ q_i ≦ 2 (1 ≦ i ≦ Q)
- 1 ≦ I_i ≦ N (1 ≦ i ≦ Q)
- q_i = 2 となる i が 1 つは存在する
- 入力例1
-
10 4
1 3 7 8
10
2 3
1 2
2 3
2 10
2 8
1 7
2 10
1 7
1 7
2 7
- 出力例1
-
1
2
4
4
5
3
