P2343 宝石管理系统

#include<iostream>
using namespace std;
#define N 100000 + 10000 + 1
namespace Splay
{
    struct node
    {
        int son [ 2 ] , siz , cnt , fa , k ;
        node(){ son [ 0 ] = son [ 1 ] = siz = cnt = fa = k = 0 ; }
    }e [ N ];
    int root , code ;
    int ls ( int x )
    {
        return e [ x ] . son [ 0 ];
    }
    int rs ( int x )
    {
        return e [ x ] . son [ 1 ];
    }
    void get_size( int x )
    {
        e [ x ] . siz = e [ x ] . cnt + e [ e [ x ] . son [ 0 ] ] . siz + e [ e [ x ] . son [ 1 ] ] . siz;
    }
    void zig_zag ( int x )
    {
        int y = e [ x ] . fa;
        int z = e [ y ] . fa;
        int son = e [ x ] . son [ x == e [ y ] . son [ 0 ] ? 1 : 0 ];
        int yson = e [ y ] . son [ 0 ] == x ? 0 : 1;
        int zson = e [ z ] . son [ 0 ] == y ? 0 : 1;

        e [ x ] . fa = z;
        e [ z ] . son [ zson ] = x;

        e [ y ] . fa = x;
        e [ x ] . son [ yson ^ 1 ] = y;

        e [ son ] . fa = y;
        e [ y ] . son [ yson ] = son;

        get_size ( y );
        get_size ( x );
    }
    void splay_to ( int x , int TO )
    {
        while ( e [ x ] . fa != TO )
        {
            int y = e [ x ] . fa;
            int z = e [ y ] . fa;
            if ( z != TO )
                zig_zag ( ls ( y ) == x && ls ( z ) == y || rs ( y ) == x && rs ( z ) == y ? y : x );
            zig_zag ( x );
        }
        if ( TO == 0 )
            root = x;
    }
    void insert ( int x )
    {
        int now , fa;
        now = root ; fa = 0;
        while ( now != 0 && e [ now ] . k != x )
        {
            fa = now;
            now = e [ now ] . son [ e [ now ] . k < x ? 1 : 0 ] ;
        }
        if ( now != 0 )
        {
            e [ now ] . cnt ++ ;
        }
        else{
            now = ++ code;
            if ( fa )
                e [ fa ] . son [ x > e [ fa ] . k ] = now;
            e [ now ] . fa = fa ;
            e [ now ] . cnt ++;
            e [ now ] . siz ++ ;
            e [ now ] . k = x;
        }
        splay_to ( now , 0 );
    }
    int find_kth ( int now , int kth )
    {
        if ( e [ ls ( now ) ] . siz >= kth )
            return find_kth ( ls ( now ) , kth );
        if ( e [ ls ( now ) ] . siz + e [ now ] . cnt >= kth )
            return e [ now ] . k;
        return find_kth ( rs ( now ) , kth - e [ now ] .cnt - e [ ls ( now ) ] . siz );
    }
}
int n , m;
int main()
{
    // freopen ( "text.in" , "r" , stdin );
    cin >> n >> m;
    for ( int i = 1; i <= n ; i ++ )
    {
        int x;
        cin >> x;
        Splay :: insert ( x ) ;
    }
    for ( int i = 1; i <= m ; i ++ )
    {
        int op , x;
        cin >> op >> x;
        if ( op == 1 )
        {
            cout << Splay :: find_kth ( Splay :: root , n - x + 1 ) << endl;
        }
        else
        {
            Splay :: insert ( x );
            n ++ ;
        }
    }
    return 0;
}