시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB118540533236.245%

문제

바이너리 왕국의 불쌍한 하인들은 매일 바이너리 길을 청소한다. 바이너리 길은 N개의 0 또는 1로 이루어진 수열이다.

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번 시련이 주어졌을 때, 하인들의 외침을 개행으로 구분하여 출력하라.

예제 입력 1

5 9
0 0 0 0 0
0
1 4
0
1 4
0
1 2
0
1 3
0

예제 출력 1

0
1
1
2
1

출처

University > 서강대학교 > 2018 Sogang Programming Contest > Champion A번

  • 문제를 만든 사람: gs15120
  • 잘못된 데이터를 찾은 사람: jh05013