Recovering permutation from its image sequence
Exactly like the bookshelf problem

This problem is exactly the same problem as the bookshelf problem that I previously reviewed.  If you work from the end of the inversion sequence, each number is like a book that you remove from the right end of the shelf.  For example, if the inversion sequence were:

Inversion sequence = 0 1 0 2 2 1 2 0


Then starting with the last entry 0, this means that book #8 is the rightmost book on the shelf.  So we can place it there:

Original sequence = ? ? ? ? ? ? ? 8


Next in the inversion sequence is 2.  This means that we book #7 is the 3rd remaining book from the right of the shelf (3rd because 0, 1, 2).

Original sequence = ? ? ? ? 7 ? ? 8


Next is 1, so book #6 is the 2nd from the right:

Original sequence = ? ? ? ? 7 6 ? 8


And you keep going until you fill in the full sequence: 2 4 5 1 7 6 3 8.

\$O(\log ^2(n))\$ solution

Just like with the bookshelf problem, this can be done in \$O(\log ^2*(n))\$ time using a binary indexed tree and a binary search of that tree.  I took the exact code I wrote for the bookshelf problem and adapted it to this one:

#include &lt;iostream&gt;
#include &lt;vector&gt;

static inline int BIT_GET(const std::vector&lt;int&gt; &amp;BIT, int i)
{
    int ret = 0;
    i++;
    while (i &gt; 0) {
        ret += BIT[i-1];
        i -= (i &amp; -i);
    }
    return ret;
}

static inline void BIT_ADD(std::vector&lt;int&gt; &amp;BIT, int i, int val)
{
    int max = BIT.size();
    i++;
    while (i &lt; max)
    {
        BIT[i-1] += val;
        i += (i &amp; -i);
    }
}

int bsearch(const std::vector&lt;int&gt; &amp;BIT, int index)
{
    int low  = 0;
    int high = BIT.size()-1;

    while (low &lt;= high) {
        int mid    = low + ((high-low)&gt;&gt;1);
        int midVal = mid + BIT_GET(BIT, mid);

        if (midVal &gt;= index)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}

int main(void)
{
    int n;
    std::cin &gt;&gt; n;
    std::vector&lt;int&gt;inv(n);
    std::vector&lt;int&gt;original(n);
    std::vector&lt;int&gt;BIT(n);

    for (int i=0;i&lt;n;i++)
        std::cin &gt;&gt; inv[i];

    for (int i=n-1;i&gt;=0;i--) {
        int index = bsearch(BIT, inv[i]);
        original[n - 1 - index] = i + 1;
        BIT_ADD(BIT, index, -1);
    }

    for (int i=0;i&lt;n;i++)
        std::cout &lt;&lt; original[i] &lt;&lt; " ";

    return 0;
}


As you can see, only main() changed.  The only tricky thing is that the BIT can only track books being removed and the books on the right shifting left by one.  The problem calls for removing books from the right and the books on the left shifting to the right by one.  So the BIT actually tracks the bookshelf in reverse order.  That is why we when we retrieve index from the BIT, we reverse it to n - 1 - index in order to determine where to place the current value in the original array.