식물원 방문 기록
실버 I의견: 0
봄의 식물원에 하루 동안 \(N\)번의 방문 기록이 남아 있다. \(i\)번째 기록에는 방문자 ID \(v_i\)가 적혀 있다. 같은 방문자가 여러 번 방문할 수 있다.
운영팀은 \(Q\)개의 구간 질문을 한다. 각 질문은 두 정수 \(l\), \(r\) \((1 \le l \le r \le N)\)로 이루어지며, \(l\)번째부터 \(r\)번째 기록까지 등장하는 서로 다른 방문자 ID의 수를 묻는다. 각 질문에 답하여라.
- \(1 \le N, Q \le 100\,000\)
- 모든 방문자 ID는 \(1\) 이상 \(10^9\) 이하의 정수이다.
- 각 질문에서 \(1 \le l \le r \le N\)이다.
첫째 줄에 기록 수 \(N\)과 질문 수 \(Q\)가 공백으로 구분되어 주어진다.
둘째 줄에 방문자 ID \(v_1, v_2, \ldots, v_N\)이 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 질문 \(l\), \(r\)이 공백으로 구분되어 주어진다.
\(Q\)개의 줄에 걸쳐 각 질문에 대한 답을 순서대로 출력한다.
7 4
3 1 2 1 3 2 4
1 4
3 6
1 7
2 2
3
3
4
1
\([1,4]\) 구간의 방문자는 \(3,1,2,1\)이므로 서로 다른 방문자는 \(3\)명이다. \([3,6]\)은 \(2,1,3,2\)로 \(3\)명, \([1,7]\)은 \(3,1,2,1,3,2,4\)로 \(4\)명, \([2,2]\)는 \(1\)로 \(1\)명이다.
4 3
5 5 5 5
1 4
2 3
1 1
1
1
1
모든 방문자가 \(5\)번이므로 구간의 크기와 무관하게 항상 \(1\)명이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
식물원 방문 기록
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
식물원 방문 기록