P12391 「RiOI-6」帝国少女

 小萝卜喜欢帽子哥哥。有多喜欢呢？每次和他出去玩都要计划好久的！ 萝卜呢，有很多件好看的衣服。因此计划的一部分就是：每次出去玩都和上次穿的不一样。 可是原先的计划表非常不合理，因此小萝卜需要花很多时间来修改。因为出去玩的时间非常宝贵，所以她认为修改次数要尽量小。

萝卜有 $m$ 件衣服，计划表为长为 $n$ 的序列 $a$，则 $a_i$ 为 $[1,m]$ 中的整数，表示当天穿的是哪一件衣服。**萝卜保证他的衣服至少有两件。** 萝卜每次修改可以将 $a_i$ 修改为 $[1,m]$ 中任何一个整数。对于一个序列 $a$，他的**困难程度**定义为：使得 $a_1,a_2,\cdots,a_n$ 中任意相邻两个数都不同的最小操作次数。设这个值为 $f(a,m)$。 对于序列 $a$，萝卜想请你求出其所有子段的困难程度之和，即： $$\sum_{1\le l\le r\le n}f([a_l,a_{l+1},\cdots,a_r],m)$$

无

无

**【样例解释】** 对于样例 $1$ 的整个原序列，一种最优的修改方案是将其修改为 $[2,1,2,1,2,1,2,1,2,1]$，修改次数是 $4$，故困难程度为 $4$。 对于样例 $2$，所有子段及其困难程度如下： - $[2]$，困难程度为 $0$。 - $[2,2]$，困难程度为 $1$。 - $[2,2,3]$，困难程度为 $1$。 - $[2]$，困难程度为 $0$。 - $[2,3]$，困难程度为 $0$。 - $[3]$，困难程度为 $0$。 故总和为 $2$。 对于样例 $3$，暂时不能给你一个明确的答复。 **【数据范围】** **本题开启捆绑测试。** |子任务|分数|$n\le$|$m\le$|特殊性质| |:-:|:-:|:-:|:-:|:-:| |$1$|$10$|$10$|$10$|| |$2$|$20$|$10^3$|$10^9$|| |$3$|$30$|$2\times10^5$|$10^9$|$m>2$| |$4$|$40$|$2\times10^5$|$10^9$|| 对于 $100\%$ 的数据，$1\le n\le 2\times10^5$，$2\le m\le 10^9$。