#P16345. [2026年山东第二轮集训]最优化题

    ID: 15556 传统题 3000ms 1024MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2600图论数学枚举贪心动态规划算法基础排序

[2026年山东第二轮集训]最优化题

题目描述

给定正整数 nn。下面称长度为 nn、每项元素均属于 [1,n]∩Z[1,n]\cap\mathbb Z 的序列为一个好序列。

对于一个好序列 a=(a1,a2,…,an)a=(a_1,a_2,\ldots,a_n),定义 f(a)f(a) 如下:

  • 将 aa 视作一张有 nn 个点、每个点恰好有一条出边的有向图,点 ii 的出边指向点 aia_i;
  • 有 nn 个人,编号为 1,2,…,n1,2,\ldots,n;在时刻 00,编号为 uu 的人站在点 uu;
  • 对于时刻 tt 站在点 uu 上的人,其在时刻 t+1t+1 走到点 aua_u;
  • 记编号为 uu 的人在时刻 tt 所处的点为 idxu,tidx_{u,t};
  • 定义
$$f(a)=\max_{\substack{t\ge 0\\1\le u\le n}} \sum_{i=1}^{n}[idx_{i,t}=u],$$

其中 [P][P] 表示命题 PP 成立时取 11,否则取 00。

给定一个好序列 bb。对于每个 0≤k≤n0\le k\le n,考虑所有能够从 bb 出发、修改至多 kk 个元素后得到的好序列 b′b',求 f(b′)f(b') 的最大值。

输入格式

第一行一个整数 nn。

第二行 nn 个整数 b1,b2,…,bnb_1,b_2,\ldots,b_n。

输出格式

输出一行 n+1n+1 个整数,依次表示 k=0,1,…,nk=0,1,\ldots,n 时的答案。

样例

样例 1

输入

10
1 1 10 1 5 6 5 8 8 1

输出

5 7 9 10 10 10 10 10 10 10 10

数据范围

1≤n≤105,1≤bi≤n.1\le n\le 10^5,\qquad 1\le b_i\le n.

子任务

子任务编号 n≤n\le 特殊性质 分值
1 1010 无 10
2 30003000 40
3 10510^5 A 10
4 B
5 无 30

特殊性质:

  • A: 所有 bib_i 均在 [1,n][1,n] 内独立均匀随机生成;
  • B: 序列 bb 中至多有 100100 种不同的元素。