题意：
在二维坐标平面内进行n (1 ≤ n ≤ 2·105)
次操作。一共有三种类型操作。
1.add x,y 将点(x,y)加进坐标系。
2.remove x,y 将点(x,y)移除.
3.find x,y 找到点(x,y)右上角的点(xp>x,yp>y)。如果有多个输出x最小的。还是有多个输出y最小的。
x,y均为非负数。以上操作均合法。
思路：
我们可以用N个set维护很坐标为i的y有哪些。当然需离线对x离散化。这题关键是询问有点难对付。如果我们知道find x,y操作时。最小的满足的x是多少。我们就可以在对应的set里找最小满足的y了。所以怎样快速找到x就是突破点了。我们可以用一颗线段树维护x为v时y的最大值。这样我们只要查询x比v大的区间能否满足在二分就可以快速定位最小的满足的x了。
详细见代码：
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=200010;
typedef long long ll;
#define lson L,mid,ls
#define rson mid+1,R,rs
struct node
{
int x,y,id;
char cmd[20];
void init(){ scanf("%s%d%d",cmd,&x,&y); }
} q[maxn];
set<int> st[maxn];
int mav[maxn<<2],H[maxn];
int n,m;
void build(int L,int R,int rt)
{
mav[rt]=-1;
if(L==R)
return;
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
build(lson);
build(rson);
}
void update(int L,int R,int rt,int p)
{
if(L==R)
{
if(st[L].size())
mav[rt]=*(--st[L].end());
else
mav[rt]=-1;
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(p>mid)
update(rson,p);
else
update(lson,p);
mav[rt]=max(mav[ls],mav[rs]);
}
int qu(int L,int R,int rt,int l,int r,int x)
{
if(mav[rt]<=x||l>r)
return -1;
if(L==R)
return L;
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1,tp=-1;
if(l<=mid)//想想怎样才会到左子树查。
tp=qu(lson,l,r,x);
if(tp!=-1)
return tp;
if(r>mid)
return qu(rson,l,r,x);
}
void init()
{
sort(H,H+m);
m=unique(H,H+m)-H;
}
int Hash(int x)
{
return lower_bound(H,H+m,x)-H;
}
int main()
{
int i,h,p;
while(~scanf("%d",&n))
{
m=n;
for(i=0;i<n;i++)
q[i].init(),H[i]=q[i].x;
init();
build(1,m,1);
for(i=0;i<n;i++)
{
h=Hash(q[i].x)+1;
if(q[i].cmd[0]=='a')
st[h].insert(q[i].y),update(1,m,1,h);
else if(q[i].cmd[0]=='r')
st[h].erase(q[i].y),update(1,m,1,h);
else
{
p=qu(1,m,1,h+1,m,q[i].y);//m打成n调了好久。。。。
if(p==-1)
printf("-1\n");
else
printf("%d %d\n",H[p-1],*st[p].upper_bound(q[i].y));//upper>.lower>=的第一个
}
}
}
return 0;
}