可能なすべての点のペア間の力の総和を求めますか？</p> <p>位置（軸）から二点& B間</p> <p>ジャンル値（整数）</p> <p>ジャンル力：

Question

それぞれ有する二つの属性を持つn点があります次式で与えられる。

Attraction_force(A, B) = (distance between them) * Max(Attraction_val_A, Attraction_val_B); 

l可能な全ての点の間の力？

私はすべてのペア

for(int i=0; i<n-1; i++) { 
    for(int j=i+1; j<n; j++) { 
     force += abs(P[i].pos - P[j].pos) * max(P[i].attraction_val, P[j].attraction_val); 
    } 
} 

例との間の力を計算し、追加することによって試み：

Points   P1 P2 P3 
Points distance: 2 3 4 
Attraction Val: 4 5 6 

Force = abs(2 - 3) * max(4, 5) + abs(2 - 4) * max(4, 6) + abs(3 - 4) * max(5, 6) = 23 

しかし、これははO（n^2）時間、私はできない取りますそれをさらに減らす方法を考える！

Answer 1

ソリューションのスキーム：

1. ソート彼らの魅力値によってすべてのポイントとそれらを一つ一つを処理し、最低の魅力と1から始まります。
2. 各ポイントについて、以前に加算されたすべてのポイントまでの距離の合計をすばやく計算する必要があります。これは、セグメントツリーやBITのようなオンラインのRange Sum Query問題解決法を使用して行うことができます。重要なアイデアは、左のすべての点が実際には違わず、座標の合計がそれらの距離の合計を計算するのに十分であるということです。
3. 新しく追加されたポイントごとに、その距離の合計（ステップ2で得られたもの）にポイントのアトラクション値を乗算し、それを答えに加えます。私はこの解決策を考案するためになさ

直感的な所見：

1. 我々は（多少「離散」）ここでは二つの「悪い」の機能を持っている：maxとモジュロ（距離）。
2. maxは、ポイントをソートして特定の順序で処理することで取り除くことができます。
3. ポイントを左と右に別々に処理すると、モジュロを取り除くことができます。
4. これらの変換のすべてを行った後、単純な代数変換の後にオンラインのRSQ問題に変換するものを計算する必要があります。

Answer 2

のアルゴリズム：あなたはすべての可能な対の間の実際の距離を必要とするので

O（N ）

は、最適です。