link of the problem is : https://www.spoj.com/problems/TPGA/

i am solving spoj problem in which i have to find the rank of the permutations when the integers lexicographically arranged means eg.

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

rank of 132 is 2. now i want to know how can i solve this using binary index tree ,i found this problem on coding portal in which this problem was queued under the Binary Index Problems someone help. give idea at least.

Auto comment: topic has been updated by ak3899 (previous revision, new revision, compare).I got accepted using SegmentTree. Let

nnumber of items in permutation. Just look on the first item of permutationa_{1}, we can say that before current permutation there are (a_{1}- 1)·(n- 1)! permutations. Then we need to erase itema_{1}and continue from next item. SegmentTree or Fenwick can answer on question "how many not erased items beforea_{i}?" inO(log(n)): for each item we set 0 when it erased and 1 when it not erased.Example