SPOJ3273——ORDERSET - Order statistic set(Treap)

In this problem, you have to maintain a dynamic set of numbers which support the two fundamental operations
INSERT(S,x): if x is not in S, insert x into S DELETE(S,x): if x is in S, delete x from S and the two type of queries
K-TH(S) : return the k-th smallest element of S COUNT(S,x): return the number of elements of S smaller than x Input Line 1: Q (1 ≤ Q ≤ 200000), the number of operations In the next Q lines, the first token of each line is a character I, D, K or C meaning that the corresponding operation is INSERT, DELETE, K-TH or COUNT, respectively, following by a whitespace and an integer which is the parameter for that operation. If the parameter is a value x, it is guaranteed that 0 ≤ |x| ≤ 109. If the parameter is an index k, it is guaranteed that 1 ≤ k ≤ 109.
Output For each query, print the corresponding result in a single line. In particular, for the queries K-TH, if k is larger than the number of elements in S, print the word ‘invalid’.
Example Input 8 I -1 I -1 I 2 C 0 K 2 D -1 K 1 K 2
Output 122 invalid 제목: 여기 링크 내용 의 제목 을 씁 니 다. 집합 S 를 유지 하고 집합 데이터 에 대한 삽입 을 실현 하 며 삭제 하고 K 가 작 으 며 K 보다 작은 수의 개 수 를 구 합 니 다.사고: 문제 의 삽입 과 삭 제 는 모두 합 법 적 인 것 이 아니 라 삽 입 된 데이터 가 이미 존재 할 수 있 지만 기록 하 나 를 삭제 하 는 것 은 집합 에 존재 하지 않 을 수 있다 는 뜻 이다.K 가 작 으 면 k 는 집합 크기 보다 클 수 있 습 니 다. 이때 invalid 를 출력 합 니 다.분명 한 것 은 Treap 의 템 플 릿 문 제 는 불합리한 삽입, 삭제, K 작은 것 을 처리 하 는 것 입 니 다.그렇지 않 으 면 RE 가 쉽다.코드:

#include
#include
#include 
#include 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn =30100;


struct Treap {

    struct node {
        ll key, weight, cnt, size;
        node *childs[2];

        void init(ll x) {
            key = x;
            weight = rand();
            cnt = 1;
            size = 1;
            childs[0] = childs[1] = NULL;
        }
    };

    node *root;

    void update(node *&x) {
        if (x == NULL)
            return;
        ll right = 0, left = 0;
        if (x->childs[0] != NULL)right = x->childs[0]->size;
        if (x->childs[1] != NULL)left = x->childs[1]->size;
        x->size = right + left + x->cnt;
    }

    void rotate(node *&x, int t) {
        node *y = x->childs[t];
        x->childs[t] = y->childs[1 - t];
        y->childs[1 - t] = x;
        update(x);
        update(y);
        x = y;
    }

    void _insert(node *&x, ll k) {
        if (x != NULL) {
            if (x->key == k) {
                x->cnt=1;
            } else {
                int t = x->key < k;
                _insert(x->childs[t], k);
                if (x->childs[t]->weight < x->weight) {
                    rotate(x, t);
                }
            }
        } else {
            x = (node *) malloc(sizeof(node));
            x->init(k);
        }
        update(x);
    }

    void _erase(node *&x, ll k) {
        if(x==NULL)return;
        if (x->key == k) {
            if (x->cnt > 1) {
                x->cnt--;
            } else {//            ，           
                if (x->childs[0] == NULL && x->childs[1] == NULL) {
                    x->cnt = 0;
                    return;
                }
                int t;
                if (x->childs[0] == NULL)t = 1;
                else if (x->childs[1] == NULL)t = 0;
                else t = x->childs[0]->weight > x->childs[1]->weight;
                rotate(x, t);
                _erase(x, k);
            }
        } else {
            int t = x->key < k;
            if(x->childs[t]!=NULL)_erase(x->childs[t], k);
            if(x->childs[t]!=NULL&&x->childs[t]->cnt == 0)free(x->childs[t]), x->childs[t] = NULL;//      
        }
        update(x);
    }

    ll _getkth(node *&x, ll k) {
        ll t = 0;
        if (x->childs[0] != NULL)t = x->childs[0]->size;
        if (k <= t)return _getkth(x->childs[0], k);
        k -= t + x->cnt;
        if (k <= 0)return x->key;
        return _getkth(x->childs[1], k);
    }

    void _lower(node *&x,ll k,ll &ans){
        if(x->key<=k){
            ans=max(ans,x->key);
            if(x->childs[1]!=NULL)_lower(x->childs[1],k,ans);
        }else if(x->childs[0]!=NULL)_lower(x->childs[0],k,ans);
    }

    void _count(node *&x,ll k,ll &ans){
        if(x==NULL)return;
        if(x->key>=k){
            ans-=x->cnt;
            if(x->childs[1]!=NULL)ans-=x->childs[1]->size;
            if(x->childs[0]!=NULL)_count(x->childs[0],k,ans);
        }else if(x->childs[1]!=NULL)_count(x->childs[1],k,ans);
    }

    void insert(ll k) {
        _insert(root, k);
    }

    void erase(ll k) {
        _erase(root, k);
        if(root!=NULL&&root->cnt == 0)free(root), root = NULL;
    }

    ll getkth(ll k) {
        if(root==NULL||k>root->size)return -1;
        return _getkth(root, k);
    }
    void lower(ll k,ll &ans){
        _lower(root,k,ans);
    }
    void count(ll k,ll &ans){
        _count(root,k,ans);
    }
};
Treap tree;
int main() {
    srand((ll)time(NULL));
    int q;
    scanf("%d",&q);
    for(int i=0;ichar c;
        ll a;
        scanf(" %c%lld",&c,&a);
        if(c=='I')tree.insert(a);
        else if(c=='D')tree.erase(a);
        else if(c=='K'){
            ll ans=tree.getkth(a);
            if(ans==-1)printf("invalid
");
            else printf("%lld
",ans);
        }else {
            ll ans=0;
            if(tree.root!=NULL)ans=tree.root->size;
            tree.count(a,ans);
            printf("%lld
",ans);
        }
    }
    return 0;
}