页面无法加载？点击这里可能会修复。
Placeholder

#8185
子任务

독사 연합 2s 1024MB

问题

뱀 N마리는 일렬로 배치되어 있으며, i번째 뱀은 a_i​라는 독의 종류를 갖는다.
뱀들은 다음 조건을 만족할 때 독사 연합(poison snake alliance)을 형성할 수 있다:

  • 같은 독의 종류를 가진 뱀들로만 구성된다.

  • 연합 내의 모든 뱀들은 서로 x마리 이하의 거리로 떨어져 있어야 한다. 여기서 x는 [1, N] 범위 내의 정수다.

  • 모든 뱀은 정확히 하나의 독사 연합에 속해야 한다.

각 x에 대해, 형성될 수 있는 최소 독사 연합의 수를 계산하시오.


输入

첫 줄에 정수 N이 주어진다. (1≤N≤10^5)

다음 줄에 N개의 정수 a_1, \cdots, a_N이 주어진다. (1≤a_i≤N)


输出

1부터 N까지의 각각의 x에 대하여 형성될 수 있는 최소 독사 연합의 수를 각 줄에 순서대로 출력한다.


子任务

编号 分数 条件
#110分

N \le 5000

#220分

a_i \le 10

#330分

독의 종류가 최대 10번까지만 중복된다.

#440分

추가 제약 조건 없음


示例 

9
1 1 1 9 2 1 2 1 1
7
5
4
4
4
4
4
3
3

x=1인 경우와 x=2 인 경우를 보면 아래와 같이 여러 구성으로 그룹이 형성될 수 있다. (각 알파벳은 서로 다른 독사 연합을 의미한다)

Example:

       1 1 1 9 2 1 2 1 1
x = 1: A B B C D E F G G (7 개의 독사 연합)
x = 1: A A B C D E F G G (7 개의 독사 연합)
x = 2: A A A B C D C E E (5 개의 독사 연합)
x = 2: A A A B C D C D E (5 개의 독사 연합)

来源

USACO 2024 December Gold

需要登录才能编写代码。