You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
译自 ROIR 2020 Day1 T3. Борьба с рутиной
，译者ShineEternal
判断员工业绩的一个重要因素就是处理日常事务的能力。
我们考虑员工连续 n 天的工作情况，第 i 天执行的工作为 ai。
为了评估员工的工作业绩，使用以下方法：
选定一个整数 d，考虑所有 连续 d 天的日期段，对于每一段这样的日子，我们统计员工完成的不同工作的种类数。
记 Sd 表示每一段这样连续 d 天的日期段完成的不同种类工作数之和。
现在需要你来统计出 S1∼n 的值。
输入格式
输入共两行:
第一行为一个整数 n，表示工作的总天数。
第二行 n 个整数，表示每天所做的工作种类编号。
输出格式
输出共 n 个数，为 S1∼n。
5
1 3 2 1 2
5 8 8 6 3
3
10 10 10
3 2 1
提示
【样例 1 解释】
| 日期段 |
所有工种 |
不同的工种的数量 |
| 1−1 |
1 |
1 |
| 2−2 |
3 |
| 3−3 |
2 |
| 4−4 |
1 |
| 5−5 |
2 |
所以 S1=1+1+1+1+1=5。
| 日期段 |
所有工种 |
不同的工种的数量 |
| 1−2 |
1,3 |
2 |
| 2−3 |
3,2 |
| 3−4 |
2,1 |
| 4−5 |
1,2 |
所以 S2=2+2+2+2=8。
| 日期段 |
所有工种 |
不同的工种的数量 |
| 1−3 |
1,3,2 |
3 |
| 2−4 |
3,2,1 |
| 3−5 |
2,1,2 |
2 |
所以 S3=3+3+2=8。
| 日期段 |
所有工种 |
不同的工种的数量 |
| 1−4 |
1,3,2,1 |
3 |
| 2−5 |
3,2,1,2 |
所以 S4=3+3=6。
| 日期段 |
所有工种 |
不同的工种的数量 |
| 1−5 |
1,3,2,1,2 |
3 |
所以 S5=3。
【数据范围】
对于 100% 的数据， 1≤n≤2×105，1≤ai≤109。
| 任务编号 |
特殊限制 |
分值 |
| 1 |
1≤n≤50,1≤ai≤50 |
12 |
| 2 |
1≤n≤50,1≤ai≤109 |
10 |
| 3 |
1≤n≤500,1≤ai≤109 |
| 4 |
1≤n≤5000,1≤ai≤5000 |
12 |
| 5 |
1≤n≤5000,1≤ai≤109 |
10 |
| 6 |
1≤n≤2×105,1≤ai≤50 |
16 |
| 7 |
无特殊限制 |
30 |
梁泽贤 (liangzexian)