問題一覧 > 通常問題

No.3269 Leq-K Partition

レベル : / AI推定難易度 : 2050 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 43
作問者 : apricity / テスター : 👑 qand
お気に入りにしたユーザー ProblemId : 12520 / 自分の提出
問題文最終更新日: 2025-08-23 22:19:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 482 (順位表) の他の問題:

Problem Statement

You are given an integer sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$. Solve the following problem for each of $k = 1,2, \dots, N$.

  • Consider partitioning $A$ into non-empty contiguous subsequences. Each element of $A$ must belong to exactly $1$ subsequence. Find the minimum number of subsequences required for a partition in which every subsequence contains at most $k$ distinct values.

Input

$N$
$A_1\ A_2\ \dots\ A_N$

  • All input values are integers.
  • $1 \le N \le 10^5$
  • $1 \le A_i \le N$

Output

Output $N$ lines. On the $i$-th line $(1 \le i \le N)$, output the answer for $k = i$.

Sample

Sample 1
Input
10
1 2 2 3 4 6 5 7 5 4
Output
9
5
3
2
2
2
1
1
1
1

  • For $k=1$, it can be partitioned into $9$ subsequences, for example $(1),(2,2),(3),(4),(6),(5),(7),(5),(4)$.
  • For $k=2$, it can be partitioned into $5$ subsequences, for example $(1,2),(2,3),(4,6),(5,7),(5,4)$.
  • For $k=3$, it can be partitioned into $3$ subsequences, for example $(1,2,2,3),(4,6,5),(7,5,4)$.
  • For $k=4$, it can be partitioned into $2$ subsequences, for example $(1,2,2,3,4),(6,5,7,5,4)$.
  • For $k=5$, it can be partitioned into $2$ subsequences, for example $(1,2,2,3,4,6),(5,7,5,4)$.
  • For $k=6$, it can be partitioned into $2$ subsequences, for example $(1,2,2,3,4,6,5),(7,5,4)$.
  • For $k\ge 7$, it can be partitioned into $1$ subsequence, for example $(1,2,2,3,4,6,5,7,5,4)$.

Sample 2
Input
1
1
Output
1

Sample 3
Input
8
1 2 3 4 5 6 7 8
Output
8
4
3
2
2
2
2
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。