题目描述

在二维平面上有 $n$ 个点,第 $i$ 个点的位置为 $(i, \ 0)$ ,第 $i$ 个点的颜色为 $a_i$。
两个颜色相同的点 $A$ 和 $B$ 会产生一个以 $AB$ 为直径的圆,该圆的颜色和这两个点的颜色相同,求有多少对颜色不同的圆相交。

思路

这里是官方题解。

其实没有官方讲得那么复杂啦。。。我们大力简化这个问题,先直接寻找所有相交的圆,再减去相交的同色圆个数。我们首先记录对于每个位置,下一个同色点出现的位置。那么我们从左到右枚举每条可能的直径,计算左右端点之间,越过端点的另一条直径的数量。

具体实现,我们开一个树状数组,记录每个位置作为右端点可以构成几个圆。对于一个新增的点,它对右边每一个同色点的贡献都是 1,单点修改即可;更新答案其实就是区间求和。

注意一个小细节,为了避免出现如图的情况被误记录,我们在每次查询前减去这种颜色的数量即可。

代码

And in the end, the love you take, is equal to the love you make.