TOJ 47 1d-kd-tree ( STL map )

http://sprout.tw/oj/pro/47/
題目的要點在於求離一個數距離最小的數，並且支持插入和修改。先考慮如果題目只求正方向距離最小，那其實只是求 lower_bound罷了。加了一個負方向其實也只是要找以該點在數線上對稱的lower_bound。因此我們只需要維護正數和負數的兩種 map就行了。

#include <bits/stdc++.h>
using namespace std;
const int MAXX = 1e9 + 9;
const int MAXN = 1e5 + 5;

int main(){
    int n; scanf("%d", &n);
    multiset<int> msp, msn;
    while( n-- ){
        char op[ 10 ]; scanf("%s", op);
        int x; scanf("%d", &x);
        if( strcmp( op, "insert" ) == 0 ){
            msp.insert( x );
            msn.insert( -x );
        } else if( strcmp( op, "delete" ) == 0 ){
            msp.erase( msp.find( x ) );
            msn.erase( msn.find( -x ) );
        } else{
            if( msp.count( x ) ){
                printf("%d\n", x);
                continue;
            }
            auto itp = msp.lower_bound( x );
            auto itn = msn.lower_bound( -x );
            if( abs( *itp - x ) == abs( *itn - ( -x ) ) )
                printf("%d %d\n", min( *itp, -( *itn ) ), max( *itp, -( *itn ) ) );
            else if( abs( *itp - x ) < abs( *itn - ( -x ) ) )
                printf("%d\n", *itp);
            else
                printf("%d\n", -( *itn ));
        }
    }
    return 0;
}