POJ 1990 : MooFest
問題
距離xと値vを持つN個の要素が与えられる。を全ての要素の組み合わせで算出し、その総和を求めよ。
解法
Binary Index Treeを使う。以下の記事を参考にした。
http://d.hatena.ne.jp/komiyam/20110223/1298457263
c1はx以下の数を示し、c2はx+1以上の数を示している。csは個数を保持し、xsは距離を保持している。
計算量
N : 要素数
X : 距離の最大値
コード
TLEするコード