(51NOD) 1364. 最大字典序排列

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1364

很棒(?)的題目(?)

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

struct Treap
{
    Treap *lc,*rc,*fa;
    int sz,val,pri;
    int mx;
    Treap(){}
    Treap(int _val) : lc(NULL),rc(NULL),fa(NULL),sz(1),val(_val),pri(rand()),mx(_val) {}
};

int Sz(Treap* t)
{
    return t?t->sz:0;
}

int Mx(Treap* t)
{
    return t?t->mx:0;
}

void pull(Treap* t)
{
    if (!t) return;
    t->sz = 1;
    t->mx = max( max( Mx(t->lc),Mx(t->rc) ) , t->val );
    if (t->lc)
    {
        t->lc->fa = t;
        t->sz += Sz(t->lc);
    }
    if (t->rc)
    {
        t->rc->fa = t;
        t->sz += Sz(t->rc);
    }
}

Treap* merge(Treap* a,Treap* b)
{
    if (!a || !b) return a?a:b;
    else if (a->pri > b->pri)
    {
        a->rc = merge(a->rc,b);
        pull(a);
        return a;
    }
    else
    {
        b->lc = merge(a,b->lc);
        pull(b);
        return b;
    }
}

void split(Treap* t,int k,Treap* &a,Treap* &b)
{
    if (!t) a=b=NULL;
    else if (Sz(t->lc) + 1 <= k)
    {
        a=t;
        split(t->rc,k - Sz(t->lc)-1,a->rc,b);
        pull(a);
    }
    else
    {
        b=t;
        split(t->lc,k,a,b->lc);
        pull(b);
    }
}

int Q(Treap* t)
{
   int ret = Sz(t->lc) + 1;
   while (t->fa != NULL)
   {
       if (t->fa->rc == t)
       {
           ret += Sz(t->fa->lc) + 1;
       }
       t = t->fa;
   }
   return ret;
}

const int N = 100006;

int a[N];

Treap *p[N];

void show(Treap* t)
{
    if (!t) return;
    show(t->lc);
    printf("%d\n",t->val);
    show(t->rc);
}

int main ()
{
    int n,k;
    scanf("%d %d",&n,&k);
    for (int i=1;n>=i;i++)
    {
        p[i] = new Treap(i);
    }
    Treap* root = NULL;
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&a[i]);
        root = merge( root, p[ a[i] ] );
    }
    for (int i=1;n-1>=i;i++)
    {
        //find the maximum number among the first k elements
        if (k == 0) continue;
        Treap *tl,*tr;
        split(root,i-1,tl,root);
        split(root,k+1,root,tr);
        int mx = Mx(root);
        int _ = Q(p[mx]);
        k -= (_-1);
        //cout << "mx = "<<mx<< " , _ = "<<_<<endl;
        Treap *_1,*_2;
        split(root,_-1,_1,root);
        split(root,1,_2,root);
        root = merge( merge( _2,_1 ),root );
        root = merge( merge(tl,root),tr );
    }
    show(root);
}