#3259. 「ROIR 2020 Day 1」对常规的斗争

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ShineEternal

题目描述

译自 ROIR 2020 Day1 T3. Борьба с рутиной

判断员工业绩的一个重要因素就是处理日常事务的能力。

我们考虑员工连续 n 天的工作情况,第 i 天执行的工作为 a_i

为了评估员工的工作业绩,使用以下方法:

选定一个整数 d ,考虑所有 连续 d 天的日期段,对于每一段这样的日子,我们统计员工完成的不同工作的种类数。

S_d 表示每一段这样连续 d 天的日期段完成的不同种类工作数之和。

现在需要你来统计出 S_{1\sim n} 的值。

输入格式

输入共两行:

第一行为一个整数 n ,表示工作的总天数。

第二行 n 个整数,表示每天所做的工作种类编号。

输出格式

输出共 n 个数,为 S_{1\sim n}

样例

样例输入 1

5
1 3 2 1 2

样例输出 1

5 8 8 6 3

样例解释 1

  • S_1 :
日期段 所有工种 不同的工种的数量
1-1 1 1
2-2 3
3-3 2
4-4 1
5-5 2

所以 S_1=1+1+1+1+1=5

  • S_2 :
日期段 所有工种 不同的工种的数量
1-2 1,3 2
2-3 3,2
3-4 2,1
4-5 1,2

所以 S_2=2+2+2+2=8

  • S_3 :
日期段 所有工种 不同的工种的数量
1-3 1,3,2 3
2-4 3,2,1
3-5 2,1,2 2

所以 S_3=3+3+2=8

  • S_4 :
日期段 所有工种 不同的工种的数量
1-4 1,3,2,1 3
2-5 3,2,1,2

所以 S_4=3+3=6

  • S_5 :
日期段 所有工种 不同的工种的数量
1-5 1,3,2,1,2 3

所以 S_5=3

样例输入 2

3
10 10 10

样例输出 2

3 2 1

数据范围与提示

对于 100\% 的数据, 1\leq n\leq 2\times 10^5 1\leq a_i\leq 10^9

任务编号 特殊限制 分值
1 1\leq n \leq 50, 1 \leq a_i \leq 50 12
2 1\leq n \leq 50, 1 \leq a_i \leq 10^9 10
3 1\leq n \leq 500, 1 \leq a_i \leq 10^9
4 1\leq n \leq 5000, 1 \leq a_i \leq 5000 12
5 1\leq n \leq 5000, 1 \leq a_i \leq 10^9 10
6 1\leq n \leq 2\times 10^5, 1 \leq a_i \leq 50 16
7 无特殊限制 30