自动搬运

查看原文

来自洛谷，原作者为

	云浅知处 喵

搬运于2025-08-24 21:40:17，当前版本为作者最后更新于2020-08-14 16:55:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

更好的阅读体验？

注：洛谷博客区表格渲染已经炸掉=_=，还是在题解区吧QAQ

$\Huge\mathsf{My\ Blog}$

---

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

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

1. $x,y,z$ 是整数,$x<y<z,y-x=z-y$；
2. $x,z$ 颜色相同。

满足上述条件的三元组的分数规定为 $(x+z) \times (number\_x+number\_z)$。

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

于是，秒懂：

$$\because y-x=z-y$$ $$\therefore x+z=2y$$

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

这就是 $y$ 的用处啦QAQ。

---

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

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

举个例子：

格子编号	1	2	3	4	5	6	7	8	9	10
格子上的数字	5		3	2	2	2	7	8	2	5
格子颜色	2		1			1	2			1

那么先按照颜色分类：

颜色为 $1$ 的：

格子编号	3	4	6	10
格子上的数字	3	2		5
格子颜色	1

颜色为 $2$ 的：

格子编号	1	2	5	7	8	9
格子上的数字	5		2	7	8	2
格子颜色	2			2

再按照编号分类：

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

格子编号	3
格子上的数字	3
格子颜色	1

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

格子编号	4	6	10
格子上的数字	2		5
格子颜色	1

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

格子编号	1	5	7	9
格子上的数字	5	2	7	2
格子颜色	2		2

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

格子编号	2	8
格子上的数字	5	8
格子颜色	2

好的，分类完毕！

那么，怎么计算分数呢？

---

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

不过，复杂度铁定爆炸。

考虑更优的做法。

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

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

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

$i$	$1$	$2$	$3$	$4$
$f[i]$	1	5	7	9
$n[i]$	5	2		2

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

$$(f[1]+f[2])\times(n[1]+n[2])$$

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

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

$$(f[1]+f[3])\times(n[1]+n[3])$$

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

$$(f[2]+f[3])\times(n[2]+n[3])$$

所以多出来的分数为：

$$(f[1]+f[3])\times(n[1]+n[3])+(f[2]+f[3])\times(n[2]+n[3])$$

展开后，得到：

$$f[1]\cdot n[1]+f[1]\cdot n[3]+f[3]\cdot n[1]+f[3]\cdot n[3]+f[2]\cdot n[2]+f[2]\cdot n[3]+f[3]\cdot n[2]+f[3]\cdot n[3] $$

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

$$f[1]\cdot n[1]+\color{red}f[1]\cdot n[3]\color{black}+\color{skyblue}f[3]\cdot n[1]\color{black}+\color{red}f[3]\cdot n[3]\color{black}+f[2]\cdot n[2]+\color{red}f[2]\cdot n[3]\color{black}+\color{skyblue}f[3]\cdot n[2]\color{black}+\color{skyblue}f[3]\cdot n[3] $$

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

$$n[3]\cdot(f[1]+f[2]+ f[3])+f[3]\cdot(n[1]+n[2]+n[3])+n[1]\cdot f[1]+n[2]\cdot f[2] $$

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

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

---

到了这一步之后，代码实现基本已经没有任何难度了=_=

所以，就不放啦QAQ。