Cod sursă (job #812438)

#include <fstream>
#define max_bit 16
#define dim 100000
using namespace std;
ifstream fin ("arbperm2.in");
ofstream fout ("arbperm2.out");
int n,k,v[dim+1],pos_perm[dim+1],perm[dim+1];
struct AIB
{
    int v[dim+1];
    void prep (int val)
    {
        for (int i=1; i<=n; i++)
            v[i]=(i&-i)*val;
    }
    void update (int pos,int val)
    {
        pos++;
        for (int i=pos; i<=n; i+=(i&-i))
            v[i]+=val;
    }
    int query (int pos)
    {
        pos++;
        int sol=0;
        for (int i=pos; i>0; i-=(i&-i))
            sol+=v[i];
        return sol;
    }
    int get_pos (int k)
    {
        k++;
        int sol=0,pos=0;
        for (int bit=max_bit; bit>=0; bit--)
        {
            int posn=(pos+(1<<bit));
            if (posn<=n&&sol+v[posn]<k)
            {
                pos=posn;
                sol+=v[posn];
            }
        }
        return pos;
    }
};
AIB aib_init,aib_fin;
void get_perm ()
{
    fin>>n>>k;
    for (int i=0; i<n; i++)
    {
        fin>>v[i];
        pos_perm[v[i]]=i;
    }
}
void get_pos ()
{
    aib_init.prep (0),aib_fin.prep (1);
    for (int i=n; i>0; i--)
    {
        int pos=pos_perm[i]-aib_init.query (pos_perm[i]);
        int bl=pos/i,br=(pos+k)/i;
        aib_init.update (pos_perm[i],1),pos=(pos+k)%i;
        int posn=aib_fin.get_pos (pos);
        perm[posn]=i,aib_fin.update (posn,-1);
        k=br-bl;
    }
}
void print_perm ()
{
    for (int i=0; i<n; i++)
        fout<<perm[i]<<" ";
}
int main()
{
    get_perm ();
    get_pos ();
    print_perm ();
    return 0;
}