Binary Kingdom
InterviewTime limit2sMemory limit512 MB
Maintain a binary array under requests that set a cell to 1 and report how many runs of consecutive 1s exist.
- Level
Medium4 of 10
- Topics
- Array, Implementation, Simulation
- Solved
- No attempts yet
Problem
The pitiful servants of the Binary Kingdom clean the Binary Road every day. The Binary Road is a sequence of N values, each 0 or 1.
A 0 is a clean cell, and a 1 is a dirty cell.
The servants clean using only a technique called "flip". It makes a run of consecutive dirty cells clean, that is, it turns all consecutive 1s into 0s.
The wicked king of the Binary Kingdom enjoys giving the servants M trials each day. There are two kinds of trials.
- "0": the servants must cry out the minimum number of "flip" operations needed to make every cell of the road clean.
- "1 i": dirty the i-th cell of the Binary Road. If it is already dirty, nothing happens.
Print the sad cries of the pitiful servants of the Binary Kingdom.
Input
The first line gives the number of cells N of the Binary Road and the number of trials M. (1 ≤ N, M ≤ 1,000,000)
The second line gives the current state of the Binary Road as N values.
The next M lines give the trials. A type 0 trial is given as "0", and a type 1 trial is given as "1 i". (1 ≤ i ≤ N)
Output
For each type 0 trial, print the servants' cry, one per line.