2015年1月3日 星期六

2014/01/03 ZJ d794: 世界排名

/*
    練習刻 Treap
    以這題來說 Treap 
    會比線段樹 好co OwO
*/
// http://zerojudge.tw/ShowProblem?problemid=d794
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>

using namespace std;

typedef long long ll;

struct Treap
{
    Treap *l, *r;
    ll pri, key, size;

    Treap(int _key)
    {
        l = r = NULL;
        pri = rand();
        key = _key;
        size = 1;
    }
};

Treap *root;

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

void pull(Treap *t)
{
    t->size = size(t->l)+size(t->r)+1;
}

Treap* merge(Treap *a, Treap *b)
{
    if( !a || !b ) return a ? a : b;

    if( a->pri >= b->pri )
    {
        a->r = merge(a->r, b);
        pull(a);
        return a;
    }
    else
    {
        b->l = merge(a, b->l);
        pull(b);
        return b;
    }
}

void split(Treap *t, Treap *&a, Treap *&b, int k)
{
    if( !t ) a = b = NULL;
    else if( t->key <= k )
    {
        a = t;
        split(t->r, a->r, b, k);
        pull(a);
    }
    else
    {
        b = t;
        split(t->l, a, b->l, k);
        pull(b);
    }
}

void insert(int x)
{
    Treap *l, *r;
    split(root, l, r, x);
    root = merge(merge(l, new Treap(x)), r);
}

int find(Treap *t, int x)
{
    if( t->key == x ) return size(t->r);
    else if( t->key < x ) return find(t->r, x);
    else return size(t->r)+1+find(t->l, x);
}

int N;

int main()
{
    srand(time(NULL) );

    while( scanf("%d", &N) != EOF )
    {
        root = NULL;

        for(int Ni = 0; Ni < N; Ni++)
        {
            ll x;
            scanf("%lld", &x);

            insert(x);
            printf("%d\n", find(root, x)+1);
        }
    }
}

沒有留言:

張貼留言