【魔怔】I Hate OI Problems.

· · 题解

你是一名 OI 教练。在一场比赛之前，你准备让你的学生更熟悉各种题型。

题库中有 n 道题目，其中第 i 道题目的题型为 a_i。在复习的时候一名学生只能刷题库中一段连续非空的题目。

身为一名教练，你想知道题库中的各种训练方式达到的效果。于是你想知道，每一个复习方案（即选题方案）中，有多少种不同的题型，输出它们的和。

即：设 f(i,j) 代表 a 中下标 [i,j] 区间内的不同数字个数，请求出 \sum\limits_{l=1}^{n} \sum\limits_{r=l}^{n}f(l,r) 的值。

你马上想到可以对于每一个 a_i，记录它上一次出现的位置 lst_{a_i}（如果没有则设为 0）。在考虑 a_i 时，忽略其他题型对结果的影响。

相比上次而言，你如果想准确地求出每种方案中不同题型的总数和，需要把左端点在 (lst_{a_i},a_i] 区间内，而右端点在 [a_i,n] 内的区间数量计入答案，这样可以保证不重不漏，证明显然。

按照你的这种思路，当遍历到 a_i 时，把最终答案加上 (i-lst_{a_i})\times (n-i+1) 即可。

这样，对于每种题型，遍历到它时都这样计算答案，就得到了计入所有题型的结果。

你的 AC 代码。

身为一名过去的 OI loser，你现在就正在为一群很可能成为 OI loser 的学生进行指导。而他们又有可能成为未来的 OI 教练。由此循环再循环。OI 也因此在。蓬勃地发展着啊。

几万人都有志于 OI，可最终只剩下几十个人成功。身为教练的你，也不知道他们会在哪里脱节。你能做的，只有让他们在这一节充分发挥自己的能力。至于他们自己，你也没办法。

你想起了你自己是 OIer 的时候，和机房的同学一起攻克难题或是摸鱼的回忆。你想起了第一次 AC 一道省选难度的题时你的快乐。你想起了你第一次 AK 模拟赛，被同学膜拜时的满足。但这一切都已经过去，一个失败者不会被人们喝彩。这些回忆只会让你感到更加悲伤。你绝望地在你的代码后面增加了几十行 // I hate OI problems，来发泄你的情绪，抒发你对 OI 题目的憎恨。

你被叫醒了。眼前的题目名称与代码重合，似乎早已有人比你更早抒发着自己的情绪。原来你在讲解一道 ABC 的 E 题时陷入了过于深刻的沉思，乃至趴倒在了桌子上。回忆与现实重叠，让你无法发话。因为，他们也是过去的你，你也是他们的未来。