SPOJ 3273 주문 통계 세트 (Treap 응용)

제목 링크: 여 기 를 클릭 ~ ~
제목:
로그 (n) 의 시간 내 에 k 대, 특정한 값 을 구 하 는 rank 를 삽입, 삭제, 반환 할 수 있 는 데이터 구 조 를 설계 합 니 다.
문제 풀이 방향:
treap 를 바탕 으로 각 노드 에 size 기록 을 추가 하여 모두 몇 개의 노드 를 포함 할 수 있 습 니까?
하루 를 조정 하여 마침내 조정 해 냈 다.힘 들 어.
null 노드 에서 size 를 가 져 올 때 특히 조심해 야 합 니 다. 그렇지 않 으 면 포인터 가 알 수 없 는 메모리 에 접근 하여 RE 를 가 져 올 수 있 습 니 다.
그래서 저 는 함 수 를 사용 하여 값 을 되 돌려 보 려 고 했 습 니 다. 과연 빈 노드 에서 size 를 취 할 수 있 습 니 다. 하하.
붙 여.

/*
    Title : Treap
    Author: nyist_xiaod
    Date  : 2013.3.19
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

template<typename T>
struct Treap
{
    struct Node
    {
        T value;
        int key,size;
        Node *lson, *rson;
        Node(const T& val):value(val),key(rand()),size(1),lson(NULL),rson(NULL){}
        int get_size(){
            return this ? size : 0;
        }
        void up(){
            if(this)
                size = lson->get_size() + rson->get_size() + 1;
        }
    };
    Node* Root;
    /**********************************************/
    Treap():Root(NULL){}
    void clear(Node* &root)
    {
        if(root == NULL)
            return ;
        clear(root->lson);
        clear(root->rson);
        delete root;
        root = NULL;
    }
    Node* search(const T& value)
    {
        for(Node *root=Root ; root ; root = value<root->value ? root->lson : root->rson)
            if(value == root->value)
                return root;
        return NULL;
    }
    void rotate_l(Node* &root)
    {
        Node* tmp = root->rson;
        root->rson = tmp->lson;
        tmp->lson = root;
        root->up();
        tmp->up();
        root = tmp;
    }
    void rotate_r(Node* &root)
    {
        Node* tmp = root->lson;
        root->lson = tmp->rson;
        tmp->rson = root;
        root->up();
        tmp->up();
        root = tmp;
    }
    void insert(Node* &root,const T& value)
    {
        if(root == NULL)
        {
            root = new Node(value);
            return ;
        }
        if(value == root->value)
            return ;
        if(value < root->value)
        {
            insert(root->lson,value);
            if(root->lson->key > root->key)
                rotate_r(root);
            else
                root->up();
        }
        else
        {
            insert(root->rson,value);
            if(root->rson->key > root->key)
                rotate_l(root);
            else
                root->up();
        }
    }
    void erase(Node* &root,const T& value)
    {
        if(root == NULL)
            return ;
        if(value == root->value)
        {
            if(root->lson && root->rson)
            {
                if(root->lson->key > root->rson->key)
                {
                    rotate_r(root);
                    erase(root->rson,value);
                }
                else
                {
                    rotate_l(root);
                    erase(root->lson,value);
                }
            }
            else
            {
                Node* tmp = root;
                root = root->rson ? root->rson : root->lson;
                delete tmp;
                return ;
            }
        }
        else
            if(value < root->value)
                erase(root->lson,value);
            else
                erase(root->rson,value);
        root->up();
    }
    Node* kth(Node* root,int k)
    {
        int lsize = root->lson->get_size();
        if(k-1 == lsize)
            return root;
        else
            if(k-1 < lsize)
                return kth(root->lson,k);
            else
                return kth(root->rson,k-lsize-1);
    }
    int rank(Node* root,const T& value)
    {
        if(root == NULL)
            return 0;
        int lsize = root->lson->get_size();
        if(value == root->value)
            return lsize + 1;
        else
            if(value < root->value)
                return rank(root->lson,value);
            else
                return lsize + 1 + rank(root->rson,value);
    }
    void insert(const T& value){
        insert(Root,value);
    }
    void erase(const T& value){
        erase(Root,value);
    }
    void kth(int k){
        if(k > Root->get_size())
            puts("invalid");
        else
            printf("%d
",kth(Root,k)->value);
    }
    void rank(const T& value){
         printf("%d
",rank(Root,value-1));
    }
    void debug(Node* u)
    {
        if(u == NULL)
            return ;
        puts("<<<");
        debug(u->lson);
        puts(">>>");
        printf(" ^^ %d ^^ prio=> %d
",u->value,u->key);
        puts(">>>>");
        debug(u->rson);
        puts("<<<<");
    }
};

int main()
{
    //freopen("in.ads","r",stdin);
    int Q,x;
    char str[8];
    Treap<int> S;
    while(~scanf("%d",&Q))
    {
        S.clear(S.Root);
        while(Q--)
        {
            scanf("%s%d",str,&x);
            if(str[0] == 'I')
                S.insert(x);
            else if(str[0] == 'D')
                S.erase(x);
            else if(str[0] == 'K')
                S.kth(x);
            else
                S.rank(x);
        }
    }
	return 0;
}