레야몬

1. 문제 길이가 N인 수열 Ai가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, ..., Aj에 가장 많이 등장하는 수가 몇 번 등장했는지 출력한다. -1- 수열의 크기 \(N(1 \leq N \leq 100,000)\) -2- A1, A2, ..., AN \((1 \leq A_{i} \leq 100,000)\) -3- 쿼리의 개수 \(M(1 \leq M \leq 100,000)\) -M개- 쿼리 i, j \((1 \leq i \leq j \leq n)\) 각 쿼리마다 정답을 한 줄에 하나씩 출력 2. 재정의 X 3. 해결방법 Sqrt Decomposition으로 나누기 isIn[A[i]]에 A[i]가 부분 수열에 몇 번 들어갔는지를 저장하기 ex) isIn[A[i]]+..

1. 문제 길이가 N인 수열 Ai이 주어진다. 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력하라. -1- 수열의 크기 \(N(1 \leq N \leq 100,000)\) -2- A1, A2, ..., AN \((1 \leq A_{i} \leq 1,000,000))\) -3- 쿼리의 개수 M \((1 \leq M \leq 100,000)\) -M개- 쿼리 i, j \((1 \leq i \leq j \leq N)\) 한 줄에 하나씩 각각의 쿼리의 정답을 출력하라. 2. 재정의 X 3. 해결 방법 쿼리 정렬로 i/sqrt(N)에 따라 정렬하고 만약 같다면 j가 큰 걸로 오름차순 정렬하기 isIn[A[i]]에 넣고 없으면 cnt++...