arrays - 吸引力作为编码

存在于N轴上的X粒子，其中每个粒子具有与其相关的两个性质，即粒子的位置及其吸引值。
两个粒子之间的引力i和j定义为：
吸引力（i，j）=距离（i，j）×最大值（吸引值[i]，吸引值[j]）
因为它们都在一条直线上
粒子等于它们位置之间的绝对差。
你应该计算一下：
∑N−1i=1∑Nj=i+1(Attraction−Force(i,j))表示
（i，n-1）和（j=i+1，n）之和（力的吸引力（i，j））
限制条件：
1≤N≤2×10^5
1≤Attraction−Value≤10^4
1≤Position≤10^4
样本输入：

3
1 2
2 4
3 6

样本输出：

22

我试了一下

import java.util.*;

class TestClass {

public static void main(String args[] ) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int a[]=new int[n];
    int b[]=new int[n];
    for(int i=0;i<n;i++)
    {
        a[i]=sc.nextInt();
        b[i]=sc.nextInt();
    }
    long sol=0;
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
          sol +=Math.abs(a[i]-a[j])*(Math.max(b[i],b[j]));
        }
    }
    System.out.println(sol);
    }

}

请让我知道是否有其他优化的方法来解决这个问题。
任何想法都会很感激的
提前谢谢

最佳答案

我认为有一个O（n log（n））算法首先是我的注释：我们要计算

S = Sum[i] Sum[j>i] abs(x[i] - x[j]) max(m[i], m[j])

在这个总和中，每个（无序的）对{i, j}只出现一次，在对粒子进行排序时，我们可以假设x[i]的位置是按升序排列的。通过对质量m[i]进行排序，我们可以得到一个数组r[1], ..., r[n]，使得m[r[i]]按升序排列。
我的想法是根据粒子的位置建立一个包含粒子的平衡二叉搜索树，这样在每个子树t的根上，一个存储子树粒子的数量和子树粒子位置的总和。
利用这些数据，对于任何实数x，可以在时间o（log（n））中确定Sum[i] abs(x - x[i])。
现在取秩r[n]的最重粒子，它对
sumS是m[r[n]] Sum[i] abs(x[r[n]] - x[i])。这种贡献可以在时间0(log(n))内计算然后，我们可以通过在平衡树上使用标准算法，或者更简单地通过修改节点上包含的数据，从二叉树中移除最重的粒子。
通过一个接一个地去除最重的颗粒，我们得到了时间S的和O(n log(n))。