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.
I got accepted using SegmentTree. Let n number of items in permutation. Just look on the first item of permutation a1, we can say that before current permutation there are (a1 - 1)·(n - 1)! permutations. Then we need to erase item a1 and continue from next item. SegmentTree or Fenwick can answer on question "how many not erased items before ai?" in O(log(n)): for each item we set 0 when it erased and 1 when it not erased.