{"problem":{"name":"[ROIR 2020] 对常规的斗争 (Day1)","description":{"content":"**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day1 T3.** ***[Борьба с рутиной ](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day1.pdf)，译者ShineEternal*** ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9785"},"statements":[{"statement_type":"Markdown","content":"**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day1 T3.** ***[Борьба с рутиной\n](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day1.pdf)，译者ShineEternal***\n\n判断员工业绩的一个重要因素就是处理日常事务的能力。\n\n我们考虑员工连续 $n$ 天的工作情况，第 $i$ 天执行的工作为 $a_i$。\n\n为了评估员工的工作业绩，使用以下方法：\n\n选定一个整数 $d$，考虑所有 连续 $d$ 天的日期段，对于每一段这样的日子，我们统计员工完成的不同工作的种类数。\n\n记 $S_d$ 表示每一段这样连续 $d$ 天的日期段完成的不同种类工作数之和。\n\n现在需要你来统计出 $S_{1\\sim n}$ 的值。\n\n## Input\n\n输入共两行:\n\n第一行为一个整数 $n$，表示工作的总天数。\n\n第二行 $n$ 个整数，表示每天所做的工作种类编号。\n\n## Output\n\n输出共 $n$ 个数，为 $S_{1\\sim n}$。\n\n[samples]\n\n## Note\n\n#### 【样例 1 解释】\n- $S_1$:\n\n| 日期段 | 所有工种 | 不同的工种的数量 |\n| :----: | :------: | :--------------: |\n| $1-1$  |   $1$    |       $1$        |\n| $2-2$  |   $3$    |       $1$        |\n| $3-3$  |   $2$    |       $1$        |\n| $4-4$  |   $1$    |       $1$        |\n| $5-5$  |   $2$    |       $1$        |\n\n所以 $S_1=1+1+1+1+1=5$。\n\n- $S_2$:\n\n|日期段|所有工种|不同的工种的数量|\n|:-:|:-:|:-:|\n|$1-2$|$1,3$|$2$|\n|$2-3$|$3,2$|$2$|\n|$3-4$|$2,1$|$2$|\n|$4-5$|$1,2$|$2$|\n\n所以 $S_2=2+2+2+2=8$。\n\n- $S_3$:\n\n|日期段|所有工种|不同的工种的数量|\n|:-:|:-:|:-:|\n|$1-3$|$1,3,2$|$3$|\n|$2-4$|$3,2,1$|$3$|\n|$3-5$|$2,1,2$|$2$|\n\n所以 $S_3=3+3+2=8$。\n\n- $S_4$:\n\n|日期段|所有工种|不同的工种的数量|\n|:-:|:-:|:-:|\n|$1-4$|$1,3,2,1$|$3$|\n|$2-5$|$3,2,1,2$|$3$|\n\n所以 $S_4=3+3=6$。\n\n- $S_5$:\n\n|日期段|所有工种|不同的工种的数量|\n|:-:|:-:|:-:|\n|$1-5$|$1,3,2,1,2$|$3$|\n\n所以 $S_5=3$。\n\n#### 【数据范围】\n对于 $100\\%$ 的数据， $1\\leq n\\leq 2\\times 10^5$，$1\\leq a_i\\leq 10^9$。\n\n|任务编号|特殊限制|分值|\n|:-:|:-:|:-:|\n|$1$|$1\\leq n \\leq 50, 1 \\leq a_i \\leq 50$|$12$|\n|$2$|$1\\leq n \\leq 50, 1 \\leq a_i \\leq 10^9$|$10$|\n|$3$|$1\\leq n \\leq 500, 1 \\leq a_i \\leq 10^9$|$10$|\n|$4$|$1\\leq n \\leq 5000, 1 \\leq a_i \\leq 5000$|$12$|\n|$5$|$1\\leq n \\leq 5000, 1 \\leq a_i \\leq 10^9$|$10$|\n|$6$|$1\\leq n \\leq 2\\times 10^5, 1 \\leq a_i \\leq 50$|$16$|\n|$7$|无特殊限制|$30$|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9785","tags":["2020","组合数学","前缀和","ROIR（俄罗斯）"],"sample_group":[["5\n1 3 2 1 2","5 8 8 6 3"],["3\n10 10 10","3 2 1"]],"created_at":"2026-03-03 11:09:25"}}