超初心者が競プロに挑む

初心者からの競プロ練習記録

ARC075Eメモ

配列A[i]がある時、A[i]<A[j]となる(i,j) (i<j)のペアの数え上げ方。
A[i]を座標圧縮して、B[i]として、B[i]の出現回数をBinaryIndexedTreeに保存しつつiを0からN-1まで巡回して下記のように数え上げる。全体でNlogN

BIT = createBinaryIndexedTree(N)
answer = 0
for i in 0..N-1
  answer += BIT.sum(0, B[i])
  BIT.add(B[i], 1)
求めたい答え=answer