(UVA) 11525 - Permutation

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=2520

可以認真的研究裡面的性質！

加油！

#include <iostream>
#include <stdio.h>
#include <ctime>
#include <cstdlib>
using namespace std;

const int MAX_N = 5e4 +6;

struct Treap {
    Treap *lc,*rc;
    int key;
    int pri;
    int sz;
    Treap(int _key) : key(_key),lc(NULL),rc(NULL),pri(rand()),sz(1) {}
};

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

void pull(Treap* t) {
    t->sz = Sz(t->lc) + Sz(t->rc) + 1;
}

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(t->key <= k) {
        a=t;
        split(t->rc,k,a->rc,b);
        pull(a);
    }
    else {
        b=t;
        split(t->lc,k,a,b->lc);
        pull(b);
    }
}

Treap* root;

void deleted(int val) {
    Treap *tl,*tr;
    split(root,val-1,tl,root);
    split(root,val,root,tr);
    root = merge(tl,tr);
}

int query(Treap* t,int cnt) {   //number cnt-th
    if (Sz(t->lc) + 1 == cnt) return t->key;
    else if (Sz(t->lc) + 1 > cnt) return query(t->lc,cnt);
    else return query(t->rc,cnt - 1 - Sz(t->lc));
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n;
        scanf("%d",&n);
        root = NULL;
        for (int i=1;n>=i;i++) root = merge(root,new Treap(i));
        for (int i=1;n>=i;i++) {
            if (i!=1) printf(" ");
            int t;
            scanf("%d",&t);
            int ret=query(root,t+1);
            deleted(ret);
            printf("%d",ret);
        }
        puts("");
    }
}