바이너리 왕국
면접 대비시간 제한2초메모리 제한512 MB
0과 1로 된 배열에서 특정 칸을 1로 바꾸는 요청과 연속된 1 구간의 개수를 묻는 요청을 처리합니다.
문제
바이너리 왕국의 불쌍한 하인들은 매일 바이너리 길을 청소한다. 바이너리 길은 0 또는 1로 이루어진 길이 N인 수열이다.
0은 깨끗한 칸, 1은 더러운 칸을 의미한다.
하인들은 "flip"이라는 기술만 사용해서 청소를 한다. 이 기술은 연속된 더러운 칸을 깨끗하게 만든다. 즉, 연속된 1을 모두 0으로 만든다.
바이너리 왕국의 악덕한 왕은 매일 하인들에게 M개의 시련을 내리는 것이 취미이다. 시련에는 2가지 종류가 있다.
- "0": 현재 길의 모든 칸을 깨끗하게 만들기 위한 "flip"의 최소 횟수를 하인들이 크게 외치게 한다.
- "1 i": 바이너리 길의 i번째 칸을 더럽힌다. 단, 이미 더럽혀져 있다면 아무 일도 일어나지 않는다.
바이너리 왕국의 불쌍한 하인들의 슬픈 외침들을 출력하라.
입력
첫째 줄에 바이너리 길의 칸의 개수 N, 시련의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)
둘째 줄에 N개의 현재 바이너리 길의 상태가 주어진다.
그다음 M개의 줄에 걸쳐서 시련이 주어진다. 이때 0번 시련은 "0", 1번 시련은 "1 i"와 같이 주어진다. (1 ≤ i ≤ N)
출력
0번 시련이 주어졌을 때, 하인들의 외침을 개행으로 구분하여 출력하라.