题解：CF19D Points

所有操作均建立在二维平面上，容易想到 STL 库的 set。将点的 $y$ 坐标放入到对应的集合 $x$ 中进行相应的操作。插入操作为 s[x].insert (y)，删除操作为 s[x].erase (y)，而查询操作需要从小到大遍历下标大于 $x$ 的集合，找到第一个不为空的集合且集合中存在一个元素大于 $y$。由题可知 $x,y$ 均较大，但是最多只有 $2 \times 10^5$ 次插入，容易想到将 $x$ 进行离散化，所以查询操作可以写成：

1 2	//对于所有 j 均满足大于 x （离散化后的编号） if (!s[j].empty () && s[j].upper_bound (q[i].y) != s[j].end ()) // print the answer

综上，我们可以得到第一份代码，只放了主函数的部分：

int main ()
{
    n = read ();
    for (int i = 1;i <= n;++i) scanf ("%s",q[i].ty),q[i].x = read (),tmp[i] = q[i].x,q[i].y = read ();
    sort (tmp + 1,tmp + 1 + n);
    tot = unique (tmp + 1,tmp + n + 1) - tmp - 1;
    for (int i = 1;i <= n;++i) q[i].id = lower_bound (tmp + 1,tmp + 1 + tot,q[i].x) - tmp;//离散化
    for (int i = 1;i <= n;++i)
    {
        if (q[i].ty[0] == 'a') s[q[i].id].insert (q[i].y);
        else if (q[i].ty[0] == 'r') s[q[i].id].erase (q[i].y);
        else 
        {
            bool ok = 0;
            for (int j = q[i].id + 1;j <= tot;++j)
            {
                if (!s[j].empty () && s[j].upper_bound (q[i].y) != s[j].end ())
                {
                    ok = 1;
                    printf ("%d %d\n",tmp[j],*s[j].upper_bound (q[i].y));
                    break;//找到最小的一个即可
                }
            }
            if (!ok) puts ("-1");//不存在就输出 -1
        }
    }
    return 0;
}

容易看得出复杂度主要在查询操作上，最坏情况下可以达到 $O(n^2)$。由于要找到一个最小的答案，所以可以进行线段树上的二分。每一个叶子节点的存的是离散化后 $x$ 对应编号的集合的最大值，换句话说，如果最大值都不符题意，那么该集合中一定无解。

将 set 与线段树配合着使用，插入的同时将离散化后 $x$ 对应编号的集合的所对应的节点改为当前集合的最大值（可能不会发生变化），删除操作也是同理，但要注意删除后集合为空的情况。

查询操作通过线段树求得对应的离散化后的 $x$ 或者无解，然后再通过 set 里的函数求解，因此主要的难度在于如何写线段树的查询操作，进行分类讨论：

区间不存在或线段树的某一个区间的最大值小于 $y$，不符，直接返回 $-1$。
已经递归至一个大小为 $1$ 的符合题意的区间（退化成点），之间返回端点编号。
递归左区间，如果合法就返回左区间的递归值；否则再递归右区间。

综上所述，我们得到了时间复杂度为 $O(n \log n)$ 的代码，一些重点在注释中有讲：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <set>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 4e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,tot,cnt,k[MAX],tree[MAX << 2]; 
struct node
{
    char ty[10];
    int x,y;
} q[MAX];
set <int> s[MAX];
void modify (int cur,int l,int r,int x,int v);
int query (int cur,int l,int r,int x,int y,int v);
int main ()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    n = read ();
    for (int i = 1;i <= n;++i) scanf ("%s",q[i].ty),q[i].x = read (),q[i].y = read (),k[++cnt] = q[i].x,k[++cnt] = q[i].y;
    sort (k + 1,k + 1 + cnt);
    tot = unique (k + 1,k + cnt + 1) - k - 1;
    for (int i = 1;i <= n;++i)//x y 都进行了离散化
    {
        q[i].x = lower_bound (k + 1,k + 1 + tot,q[i].x) - k;
        q[i].y = lower_bound (k + 1,k + 1 + tot,q[i].y) - k;//y 进行离散化是因为存在 y = 0 的点 离散化后便于与空集合作区分
    }
    for (int i = 1;i <= n;++i)
    {
        if (q[i].ty[0] == 'a') s[q[i].x].insert (q[i].y),modify (1,1,tot,q[i].x,*(--s[q[i].x].end ()));//插入后查找最值
        else if (q[i].ty[0] == 'r')
        {
            s[q[i].x].erase (q[i].y);
            if (!s[q[i].x].size ()) modify (1,1,tot,q[i].x,0);//区间为空，直接更新成 0
            else modify (1,1,tot,q[i].x,*(--s[q[i].x].end ()));//删除后查找最值
        }
        else 
        {
            int pos = query (1,1,tot,q[i].x + 1,tot,q[i].y);
            if (pos == -1) puts ("-1");//无解
            else printf ("%d %d\n",k[pos],k[*s[pos].upper_bound (q[i].y)]);//还原成原来的值后输出
        }
    }
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}
void modify (int cur,int l,int r,int x,int v)//单点更新
{
    if (l == r)
    {
        tree[cur] = v;
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) modify (cur << 1,l,mid,x,v);
    else modify (cur << 1 | 1,mid + 1,r,x,v);
    tree[cur] = max (tree[cur << 1],tree[cur << 1 | 1]);//维护最大值
}
int query (int cur,int l,int r,int x,int y,int v)
{
    if (tree[cur] <= v || y < l || x > r) return -1;//无解
    if (l == r) return l;//区间长度为 1
    int mid = (l + r) >> 1,s = query (cur << 1,l,mid,x,y,v);
    if (~s) return s;//有解 显然左区间的编号更小
    return query (cur << 1 | 1,mid + 1,r,x,y,v);//左区间无解在进行右区间的递归
}