A = {0,…,0}
クエリ1. A[i] += v; (v>0)
クエリ2. A[i]の順位

という問題に変換できる(と思う).
セグメントツリーの各ノードに「その区間でソートした列」ではなくて, 平衡2分探索木を持たせることで, クエリO((logN)^2)できそう（だが, 定数倍で死ぬ）