【题目链接】:http://hihocoder.com/problemset/problem/1329

【题意】

【题解】



插入操作:…,记住每次插入之后都要把它放到根节点去就好;

询问操作:对于询问x,然后找到权值为x+1的这个节点的左子树中的最大值;(如果没有这个x+1节点,则自己插入一个,之后删掉就好);

删除操作:插入两个节点l和r;然后找到小于l且最大的数字所在的节点lu,把它提到根节点所在的位置,然后再找到大于r且最小的数字所在的节点rv;把它提到根节点的右儿子所在的位置;

则根节点的右儿子的左子树就是需要删掉的->也即代表了[l..r]这个区间



【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 110;

struct node

{

    int val;

    node *par,*child[2];

    node(int val): val(val),par(NULL){}

};

int n;

char s[3];

node *root;

void rotate(node* const x, int c) {

    node* const y = x->par;

    y->child[c ^ 1] = x->child[c];

    if (x->child[c] != NULL) x->child[c]->par = y;

    x->par = y->par;

    if (y->par != NULL && y->par->child[0] == y) y->par->child[0] = x;

    else if (y->par != NULL && y->par->child[1] == y) y->par->child[1] = x;

    y->par = x;

    x->child[c] = y;

}

inline bool _splay_parent(node *x, node* (&y), node* stop) {

    return (y = x->par) != stop && (x == y->child[0] || x == y->child[1]);

}

void splay(node* const x, node* const stop) {

    for (node *y, *z; _splay_parent(x, y, stop); ) {

        if (_splay_parent(y, z, stop)) {

            const int c = y == z->child[0];

            if (x == y->child[c]) rotate(x, c ^ 1), rotate(x, c);

            else rotate(y, c), rotate(x, c);

        } else {

            rotate(x, x == y->child[0]);

            break;

        }

    }

    if (stop == NULL) root = x;

}

node *cr(node *u,int val)

{

    if (u->val==val) return u;

    if (u->child[val>u->val]==NULL)

    {

        node *v = new node(val);

        v->child[0] = v->child[1] = NULL;

        v->par = u;

        u->child[val>u->val] = v;

        return v;

    }

    return cr(u->child[val>u->val],val);

}

node *cz(node *v,int val)

{

    if (v->val==val) return v;

    if (v->child[val>v->val]==NULL) return NULL;

    return cz(v->child[val>v->val],val);

}

void cr(int x)

{

    node *u = cr(root,x);

    splay(u,NULL);

}

node *get_max(node * v)

{

    if (v->child[1]==NULL)

        return v;

    return get_max(v->child[1]);

}

node *get_min(node *v)

{

    if (v->child[0]==NULL)

        return v;

    return get_min(v->child[0]);

}

void sc(int l,int r)

{

    cr(l),cr(r);

    node *u = cz(root,l);

    splay(u,NULL);

    node *lu = get_max(u->child[0]);

    node *v = cz(root,r);

    splay(v,NULL);

    node *rv = get_min(v->child[1]);

    splay(lu,NULL);

    splay(rv,lu);

    rv->child[0] = NULL;

}

int query(int x)

{

    node *v = cz(root,x+1);

    bool ju = (v==NULL);

    if (ju) v = cr(root,x+1);

    splay(v,NULL);

    int k = get_max(v->child[0])->val;

    if (ju) sc(x+1,x+1);

    return k;

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use

    root = new node(-1);

    root->child[0] = root->child[1] = NULL;

    cr(21e8);

    cin >> n;

    rep1(i,1,n)

    {

        cin >> s;

        if (s[0]=='I')

        {

            int x;

            cin >> x;

            cr(x);

        }

        else

            if (s[0]=='D'){

                int l,r;

                cin >> l >> r;

                sc(l,r);

            }

            else

                if (s[0]=='Q'){

                    int x;

                    cin >> x;

                    cout << query(x) << endl;

                }

    }

    return 0;

}