学步园

题意： 给出一个二维平面，要求支持三种操作：插入一个点(x,y)，删除一个点，以及查询横坐标比给定x大，纵坐标比给定y大的具有最小横坐标的点，输出它的坐标。如果有多个点具有相同x值，输出在满足要求下y值最小的那个。操作次数20W。

解法： 把所有的点离散化后按照y值排序，那么我们需要的答案就是在满足y的情况下找到最小的满足的x值。那么就使用树状数组来实现对y~正无穷这个区间的查询。

对y轴建树，把每个点插到它的y值对应的位置，用树状数组来维护。然后对于每次的询问点(x0,y0)，查询y0+1~正无穷区间，在每个位置二分查找最小x值，最后维护一个最小值即为答案，复杂度n*(lgn)^2.

/* **********************************************
Author      : Nero
Created Time: 2013/9/2 15:13:03
Problem id  : CF-19D
Problem Name: Points
*********************************************** */

#include <stdio.h>
#include <string.h>
#include <set>
#include <algorithm>
using namespace std;
#define REP(i,a,b) for(int i=(a); i<(int)(b); i++)
#define clr(a,b) memset(a,b,sizeof(a))
typedef pair<int,int> P;
#define MP make_pair

const int INF = 0x3f3f3f3f;
const int MAXN = 201000;

// 离散化
struct San {
    int a[MAXN], n;
    int size() { return n; }
    void init() { n = 0; }
    void push(int x) { a[n++] = x; }
    void doit() { sort(a,a+n); n = unique(a,a+n) - a; }
    int operator [] (int x) { return lower_bound(a,a+n,x) - a; }
}san;

struct Query {
    char c;
    int x,y;
}q[MAXN];
int n;

// 树状数组套set
set <P> ss[MAXN];
set <P> :: iterator it;
inline void add(int p, P node) { for( ; p > 0; p -= p&-p) ss[p].insert(node); }
inline void remove(int p, P node) { for( ; p > 0; p -= p&-p) ss[p].erase(node); }
inline void query(int p, P node) {
    P ans = MP(INF,INF);
    for( ; p < san.size(); p += p&-p) {
        it = ss[p].lower_bound(node);
        if(it == ss[p].end()) continue;
        ans = min(ans, *it);
    }
    if(ans.first == INF) printf("-1\n");
    else printf("%d %d\n", ans.first, ans.second);
}

int main() {
    scanf("%d", &n);
    char s[10];
    for(int i = 0; i < n ; i ++) {
        scanf("%s%d%d", s, &q[i].x, &q[i].y);
        q[i].c = s[0];
        san.push(q[i].y);
    }
    san.doit();
    for(int i = 0; i < n; i ++) {
        if(q[i].c == 'a') add(san[q[i].y], MP(q[i].x,q[i].y));
        else if(q[i].c == 'r') remove(san[q[i].y], MP(q[i].x, q[i].y));
        else query(san[q[i].y]+1, MP(q[i].x+1, q[i].y+1));
    }
    return 0;
}