I tried to solve CF Round #261 D. Pashmak and Parmida's problem. But after some attempt I failed to figure out a solution. Then I read the Tutorial and tried to analysis author's Solution .. Still I have no clue how the author's solution is working.
Clearly I am not able to catch the idea. Please someone explain the solution (author's / your own) and help me understand the strategy.
Thanks in advance :)
That problem is actually a harder version of this problem: http://www.spoj.com/problems/INVCNT/. The idea behind this problem is to count how many times a given element appears from left to right up to the index i (you could use a map to count how many times a given element has appeared so far, and use an array to count the appearances of the i-th element from left to right). But, you still need a quick way to count how many elements j (j > i), appear from right to left less times than i-th one. That's where the Fenwick Tree comes in, as you can get that sum in O(log n), which is pretty good given the problem constrains. Because you go from right to left, and ask the Fenwick Tree, how many elements have we found that appear less times than the current one, we add that number to answer add, and add the appearances of the current number to the Fenwick Tree.
You might look at my code if you'd like: http://codeforces.net/contest/459/submission/9271246 Topcoder Tutorial on BIT (Fenwick Tree) : http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees