K番目のセットビット
サイズが
n の二進数の配列が与えられます。この配列には 0 と 1 の要素が含まれ、要素は 1 から n まで番号が振られています。ここに対して、合計 q 回のクエリを処理する必要があります。クエリには2つの種類があり、以下のいずれかを行います:- クエリタイプ1: 配列の中で 1 が出現する
k番目の位置を見つける。
- クエリタイプ2: 配列の特定のインデックスにある値を更新する。
効率的にクエリに回答するプログラムを作成してください。
入力 (Input)
最初の行には、配列のサイズを表す整数
n とクエリの数を表す整数 q が、スペース区切りで与えられます。2 行目には、長さが
n の二進数の配列の要素が入力されます。続く
q 行にはクエリの内容が与えられます。各クエリは、クエリタイプ (1 または 2) と、必要なパラメータを続けて指定します:- クエリタイプ1の場合:
k(1 ≤ k ≤ n)
- クエリタイプ2の場合: インデックス
p(1 ≤ p ≤ n) と、その位置に更新する値 ( または )
出力 (Output)
クエリタイプ1については、配列の中で 1 が
k 回目に現れるインデックスを出力してください。もし k 回目の 1 が存在しない場合は -1 を出力してください。例 (Examples)
Input | Output |
6 4
1 0 1 1 0 1
1 2
2 1 0
1 4
1 3 | 3
-1
6 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB