我遇到了一个算法问题：
完全连接
给定沿直线分布的n城市，设Xi为城市i的位置，pi为其人口。
现在，我们开始根据距离和人口在每两个城市之间铺设电缆。给定两个城市i和j，在它们之间铺设电缆的成本为|Xi-Xj|*max（Pi，Pj）。铺设所有的电缆要花多少钱？
例如，给定：
i
Xi
Pi-——--1 1 42 2 53 3 6
那么总成本可以计算为：
i
j|Xi-Xj|最大（Pi，Pj）分部成本-------------------1 2 1 5 52 3 1 61 3 2 6 12
因此，总成本为5+6+12=23。
虽然这显然可以在O（n2）时间内完成，但它能在渐近更短的时间内完成吗？
我可以想出更快的解决方案。如果我没有错，它将转到O（n*logn）。现在，让我们首先根据圆周率对所有城市进行排序。这是O（n*logn）。然后我们开始按圆周率的递增顺序处理城市。原因是-在这种情况下，你总是知道你有max（Pi，Pj）=Pi。我们只想添加所有来自与Pi关系的片段。那些将与较大索引连接的索引将在处理时进行计数。
现在我能想到的是使用几个索引树来降低算法的复杂性。第一个索引树是计算节点的数量，可以处理以下类型的查询：在对数时间内xi右边有多少节点。让我们称这个数字为NR。第二个索引树可以处理以下类型的查询：从所有点到给定x右边的距离之和是多少。这些距离被计算到一个固定点，该固定点保证在最右边的点右边，让我们称其为x XR。让我们将这个数字称为SUMD。然后，到我们点右边的所有点的距离之和可以这样找到：NR*dist（Xi，XR）-SUMD。然后所有这些对结果贡献（NR*dist（Xi，XR）-SUMD）*Pi。左边的分数也是一样，你就会得到答案。处理完第i个点后，将其添加到索引树中，然后可以继续。
编辑：以下是一篇关于Biary索引树的文章：http://community.topcoder.com/tc?module=Static&d1=教程&d2=二进制索引树
这是来自codesprint 2的直接连接问题。
他们将在一周内在自己的网站上发布所有问题的解决方案。
（他们说："现在比赛结束了，我们对每个人讨论他们的问题解决方案都很冷静。"）