记录编号	364530	评测结果	AAAAAATTTTTATTTTTTTATTTTAAAAAA
题目名称	[HZOI 2016]tb的平衡树	最终得分	46
用户昵称	sxysxy	是否通过	未通过
代码语言	C++	运行时间	42.086 s
提交时间	2017-01-16 23:14:30	内存使用	0.37 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cctype>
#include <algorithm>
using namespace std;
int L_LIMIT = 0;
int R_LIMIT = 0;
namespace IO
{
    char buf[1<<16], *fs, *ft;
    inline char readc()
    {
        return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<16,stdin), fs==ft))?0:*fs++;
    }
    inline int fast_read()
    {
        char c = readc();
        int r = 0;
        bool sig = false;
        while(c > '9' || c < '0')
        {
            if(c == '-')sig = true;
            c = readc();
        }
        while(c >= '0' && c <= '9')
        {
            r = (r<<3)+(r<<1)+(c^0x30);
            c = readc();
        }
        return sig?-r:r;
    }
}using IO::fast_read;using IO::readc;
struct node
{
    node *ls, *rs;
    int cnt;
    node()
    {
        ls = rs = NULL;
        cnt = 0;
    }
    inline void pushup()
    {
        cnt = 0;
        if(ls)
        {
            if(!ls->cnt)
            {
                delete ls;
                ls = NULL;
            }else cnt += ls->cnt;
        }
        if(rs)
        {
            if(!rs->cnt)
            {
                delete rs;
                rs = NULL;
            }else cnt += rs->cnt;
        }
    }
}*root;
void insert(node *&x, int p, int L, int R, int d = 1)
{
    if(!x)x = new node();
    if(L == R && L == p){x->cnt += d;return;}
    else 
    {
        int M = (L+R)>>1;
        if(p <= M)insert(x->ls, p, L, M, d);
        else if(p > M)insert(x->rs, p, M+1, R, d);
    }
    x->pushup();
}
int query(node *x, int ql, int qr, int L, int R)
{
    if(!x)return 0;
    if(L >= ql && R <= qr)return x->cnt;
    else{
        int r = 0, M = (L+R)>>1;
        if(ql <= M)r += query(x->ls, ql, qr, L, M);
        if(qr > M)r += query(x->rs, ql, qr, M+1, R);
        return r;
    }
}
int kth(int k)
{
    int l = L_LIMIT, r = R_LIMIT;
    int ans;
    while(l <= r)
    {
        int m = (l+r)>>1;
        if(query(root, L_LIMIT, m, L_LIMIT, R_LIMIT) >= k)
        {
            ans = m;
            r = m-1;
        }else l = m+1;
    }
    return ans;
}
int cnt;
inline int rank(int v)
{
    return query(root, L_LIMIT, v-1, L_LIMIT, R_LIMIT)+1;
}
inline int pre(int v)
{
    int k = rank(v);
    return kth(k-1);
}
inline int succ(int v)
{
    int k = query(root, L_LIMIT, v, L_LIMIT, R_LIMIT);
    return kth(k+1);    
}
int main()
{
    //freopen("test_data.txt", "r", stdin);
    freopen("tb_kp.in", "r", stdin);
    freopen("tb_kp.out", "w", stdout);
    L_LIMIT = -0x7f3f3f3f, R_LIMIT = 0x7f3f3f3f;
    int n = fast_read();
    cnt = 0;
    while(n--)
    {
        int op = fast_read();
        if(op > 6)
        {
            switch(op)
            {
                case 7:
                    printf("%d\n", kth(1));
                break;
                case 8:
                    printf("%d\n", kth(cnt));
                break;
            }
        }
        else
        {
        int v = fast_read();
        switch(op)
        {
            case 1:
                insert(root, v, L_LIMIT, R_LIMIT);
                cnt++;
            break;
            case 2:
                insert(root, v, L_LIMIT, R_LIMIT, -1);
                cnt--;
            break;
            case 3:
                printf("%d\n", rank(v));
            break;
            case 4:
                printf("%d\n", kth(v));
            break;
            case 5:
                printf("%d\n", pre(v));
            break;
            case 6:
                printf("%d\n", succ(v));
            break;
        }
        }
    }
    return 0;
}