(問題 11)ランプの切り替え part.1 Clojure(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
(はじめに)
ここからは、Segment Treeを使って問題を解いていきます。
問題 11 と問題 14 はそれぞれ問題 12 と問題 15 の問題のとっかかりとなっています。
(問題)
ランプが N 個あり、左からランプ 1,ランプ 2, ..., ランプ N と並んでいます。始め M 個のランプ ランプ A_1, ランプ A_2, ランプ A_3, ..., ランプ A_M が赤色に光っており、その他は青色に光っています。Q 個のクエリが渡されるので、それぞれのクエリを処理してください。i 番目のクエリは以下の通りです。
- 入力される値
-
入力は以下のフォーマットで与えられます。
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 ≦ 2000
- 1 ≦ A_i ≦ N (1 ≦ i ≦ M)
- i ≠ j なら A_i ≠ A_j
- 1 ≦ Q ≦ 2000
- 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
