The K-th One, Under Fire

Difficulty: 1900 4000 ms 128 MB

binary-search fenwick

A binary array changes over time: F i flips position i, and K k asks for the position of the k-th 1 (or −1 if fewer than k ones exist).

Input: the first line has N and Q; the second line has the initial 0/1 array; each of the next Q lines is an operation.

Output: one line per K query.

Constraints:

• 1 ≤ N, Q ≤ 10⁵

Sample Tests

5 4
1 0 1 1 0
K 2
F 3
K 2
K 3

3
4
-1

1 2
0
F 1
K 1

1

Read the Editorial