首先来看这个什么三元组。

定义一种特殊的三元组：(x,y,z)，其中x,y,z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：

x,y,z 是整数,x<y<z,y−x=z−y；x,z 颜色相同。

满足上述条件的三元组的分数规定为 (x+z)×(number_x+number_z)。

诶，我们发现，这个「分数」跟 y 之间，半个咕值的关系都没有啊 QAQ？

于是，秒懂：

∵y−x=z−y

∴x+z=2y

又，2y 是偶数，所以 x,z 同奇偶。

这就是 y 的用处啦QAQ。

由于不同颜色的 x,z 肯定不会产生分数，所以我们可以先把这个「狭长的纸带」按照颜色分类，最后把每种颜色产生的分数加起来即可。

然后不同奇偶性的 x,z 也不会产生分数，所以把每个颜色种类按照奇偶性再分个类，最后把奇数产生的分数和偶数产生的分数加起来即可。

举个例子：

格子编号   1 2 3 4 5 6 7 8 9 10

格子上的数字 5 5 3 2 2 2 7 8 2 5

格子颜色   2 2 1 1 2 1 2 2 2 1

那么先按照颜色分类：

颜色为 1 的：

格子编号   3 4 6 10

格子上的数字 3 2 2 5

格子颜色   1 1 1 1

颜色为 2 的：

格子编号   1 2 5 7 8 9

格子上的数字 5 5 2 7 8 2

格子颜色   2 2 2 2 2 2

再按照编号分类：

颜色为 1 ，编号为奇数的：

格子编号   3

格子上的数字 3

格子颜色   1

颜色为 1 ，编号为偶数的：

格子编号   4 6 10

格子上的数字 2 2 5

格子颜色   1 1 1

颜色为 2 ，编号为奇数的：

格子编号   1 5 7 9

格子上的数字 5 2 7 2

格子颜色   2 2 2 2

颜色为 2 ，编号为偶数的：

格子编号   2 8

格子上的数字 5 8

格子颜色   2 2

好的，分类完毕！

那么，怎么计算分数呢？

当然可以 O(n2) 暴力算一通。做法显然，这里不多说了。

不过，复杂度铁定爆炸。

考虑更优的做法。

拿上面那个例子中，颜色为 2 ，编号为奇数的 4 个格子来举个例子：

由于颜色显然是一样的，而且计算分数也和颜色无关，所以就不用再管颜色了。

然后设 f[i] 为这一组中第 i 个数的编号，n[i] 为这一组中第 i 的数的颜色。

i  1 2 3 4

f[i]1 5 7 9

n[i]5 2 7 2

先看前两个数，他们产生的分数为：

(f[1]+f[2])×(n[1]+n[2])

然后考虑当第三个数加入时，多出来的分数。

第三个数和第一个数会产生一些分数：

(f[1]+f[3])×(n[1]+n[3])

第三个数和第二个数也会产生一些分数：

(f[2]+f[3])×(n[2]+n[3])

所以多出来的分数为：

(f[1]+f[3])×(n[1]+n[3])+(f[2]+f[3])×(n[2]+n[3])

展开后，得到：

f[1]⋅n[1]+f[1]⋅n[3]+f[3]⋅n[1]+f[3]⋅n[3]+f[2]⋅n[2]+f[2]⋅n[3]+f[3]⋅n[2]+f[3]⋅n[3]

把 n[3] 和 f[3] 提取出来：

f[1]⋅n[1]+f[1]⋅n[3]+f[3]⋅n[1]+f[3]⋅n[3]+f[2]⋅n[2]+f[2]⋅n[3]+f[3]⋅n[2]+f[3]⋅n[3]

（标红的是提取出来的 n[3]，标蓝的是提取出来的 f[3]）

n[3]⋅(f[1]+f[2]+f[3])+f[3]⋅(n[1]+n[2]+n[3])+n[1]⋅f[1]+n[2]⋅f[2]

从这个式子中，我们看出，只需要处理 f 数组，n 数组，还有 f[i]⋅n[i] 的前缀和即可。

后面也是一个一个添加进来，一样的。

该题解来自洛谷