记录编号	480110	评测结果	AAAAAAAAAA
题目名称	1829.[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	Lazer2001	是否通过	通过
代码语言	C++	运行时间	0.100 s
提交时间	2017-12-25 20:38:59	内存使用	69.66 MiB

# include <cstdio>
# include <cstring>
# include <iostream>
# include <algorithm>
 
# define rep(i, s, t)  for( register __typeof ( t ) i = s, i##_end_ = t ; i <= i##_end_ ; ++ i )
 
typedef long long LL;
# define RG register
 
const int SN = 100000 + 47;
const int ST = 1 << 24 | 47;
const int INF = 0x3f3f3f3f;
 
namespace In  {
# define In_Len 2000000
    static std :: streambuf *fb ( std :: cin.rdbuf ( ) ) ;
    static char buf [In_Len], *ss ( 0 ) ;

	void init ( )  {  fb -> sgetn ( ss = buf, In_Len ) ;  }
	
    inline int read ( )  {
        register int x ;
        bool opt ( 1 ) ;
        while ( isspace ( *ss ) )  ++ ss ;
        if ( *ss == 45 )  { ++ ss ; opt = 0 ; }
        for ( x = -48 + *ss ; isdigit ( * ++ ss ) ; ( x *= 10 ) += *ss - 48 ) ; ++ ss ;
        return opt ? x : -x ;
    }
# undef pick
# undef In_Len
}
 
namespace Out  {
# define Out_Len 2000000
    std :: streambuf *fb ( std :: cout.rdbuf ( ) ) ;
    char buf [Out_Len], *ss ( buf ) ;
 
    inline void print ( register int x )  {
        static int st [30], tp ( 0 ) ;
        if ( ! x )  {  *ss ++ =  48 ; *ss ++ = 10 ; return ;  }
        if ( x < 0 )  {  *ss ++ = 45 ; x = -x ;  }
        while ( x ) st [++ tp] = x % 10 | 48, x /= 10 ;
        while ( tp )  *ss ++ = st [tp --] ;
        *ss ++ = 10 ;
    }
 
    inline void flush ( )  {  fb -> sputn ( buf, ss - buf ) ;  }
 
# undef echo
# undef Out_Len
}
 
typedef std :: pair < int, int > query, node ;

# define x first
# define y second
    
struct cmp  {
	inline bool operator ( ) ( const node& a, const node& b )  {
		return a.x < b.x ;
	}
} ;
 
query q[SN];
node a[SN];
int tree[ST], cnt;
 
# define Add(x, y) for(RG int xx=x+cnt-1,yy=y; xx; xx>>=1) *( tree + xx ) += yy
 
 
inline int QuerySum( int x) {
    RG int res = 0;
    for(RG int l=cnt, r=x+cnt; l^r^1; l>>=1, r>>=1) {
        if(~l&1) res += tree[l^1];
        if(r&1) res += tree[r^1];
    }
    return res;
}
 
inline int QueryByRank(int x) {
    RG int i = 1;
    while(i < cnt)
        (tree[i<<1] >= x) ? ( i <<= 1 ) : ( x -= tree[i<<1], i = i<<1|1 ) ; 
    return a[i-cnt+1].x;
}
 
inline int Pre(int x) {
    RG int t = x + cnt - 1;
    if(tree[t]) return a[x].x;
    while(t) {
        while(t && (~t&1)) t >>= 1;
        if(tree[t>>1] > tree[t]) {t^=1; break;}
        t >>= 1;
    }
 
    while(t < cnt) t = tree[t<<1|1] ? t<<1|1 : t<<1;
    return a[t-cnt+1].x;
}
 
inline int Nxt(int x) {
    RG int t = x + cnt - 1;
    if(tree[t]) return a[x].x;
    while(t) {
        while(t && (t&1)) t >>= 1;
        if(tree[t>>1] > tree[t]) {t^=1; break;}
        t >>= 1;
    }
    while(t < cnt) t = tree[t<<1] ? t<<1 : t<<1|1;
    return a[t-cnt+1].x;
}
 
int main() {
	freopen ( "phs.in", "r", stdin ) ;
    freopen ( "phs.out", "w", stdout ) ;
 	
 	In :: init ( ) ;
 	
    RG int n = In :: read();
    RG int tot ( 0 ) ;
    rep(i, 1, n) {
        q[i].x = In :: read(), q[i].y = In :: read( );
        if(q[i].x != 4) a[++tot] = ( node ) {q[i].y, i};
    }
 
    a[++tot] = ( node ){INF, 0}, a[++tot] = ( node ){-INF, 0}, cnt = 1;
    std::sort(a+1, a+tot+1, cmp ( ));
    rep(i, 2, tot) {
        if(a[i].x != a[i-1].x) a[++cnt] = a[i];
        q[a[i].y].y = cnt;
    }
 
    cnt = tot; while(cnt ^ (cnt&-cnt)) cnt += (cnt&-cnt);
 
    RG int x ;
    rep(i, 1, n) {
        if(q[i].x != 4) x = q[i].y;
        switch ( q [i].x )  {
			case 1 : Add(x, 1);  break;
	        case 2 : {if(tree[x+cnt-1]) Add(x, -1);} break;
	        case 3 : Out :: print (QuerySum(x-1)+1); break;
	        case 4 : Out :: print ( QueryByRank(q[i].y)); break;
	        case 5 : Out :: print ( Pre(x-1)); break;
	        case 6 : Out :: print ( Nxt(x+1)); break;
 		}
    }
	
	Out :: flush ( ) ;
	
    return 0;
 
}