레이팅 미적용설명
농부 존의 소 \(N\)마리는 \(1 \ldots N\)으로 번호가 붙어 있으며, 모두 한 줄로 서 있다(워낙 자주 줄을 서다 보니 이제는 농부 존이 살짝만 재촉해도 줄을 선다). 각 소에게는 품종 ID가 있다. 홀스타인은 1, 건지는 2, 저지는 3이다. 농부 존은 줄의 특정 구간 안에 있는 각 품종의 소 수를 세는 일을 도와주기를 바란다.
Problem credits: Nick Wu
제약
Problem credits: Nick Wu
입력 형식
입력의 첫째 줄에 \(N\)과 \(Q\)(\(1 \leq N \leq 100,000\), \(1 \leq Q \leq 100,000\))가 주어진다.
다음 \(N\)개의 줄에는 1, 2, 3 중 하나의 정수가 주어지며, 줄에 선 소 한 마리의 품종 ID를 의미한다.
다음 \(Q\)개의 줄에는 각각 두 정수 \(a, b\)(\(a \leq b\)) 형태의 질의가 주어진다.
출력 형식
\(Q\)개의 질의 \((a,b)\) 각각에 대해, \(a \ldots b\)번 소들 중 홀스타인(품종 1), 건지(품종 2), 저지(품종 3)의 수, 이렇게 세 수를 담은 줄을 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
bcount.in · 출력을 쓸 파일 bcount.out예제 1
입력
6 3
2
1
1
3
2
1
1 6
3 3
2 4출력
3 2 1
1 0 0
2 0 1문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > December > Silver
태그