|
|
题目大意： 输入给出三种操作： 1、add x y 2、remove x y 3、find x y 每次find的时候找到一个组合(X0,Y0) (X0>x,Y0>y且X0,Y0没有被移除)。 N<＝200000 比较大，不可能每次都排序， 这时线段数发挥了它强大的威力。 思路： 离线操作，先离散化，再按原来的顺序进行每一步操作，每一个区间保存本区间内y的最大值，插入和移除的时候都要及时更新。 注意离散化的时候add 与 remove同一个点的时候，不能离散为两个点。也就是离散的对象只能是add和find的坐标。就因为这个比赛的时候不停的WA。
 #include<iostream>
#include<queue>
#include<map>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
const int N = 200005;
  struct node {
 char s[10];
int x,y;
int id;
  const bool operator<(const node &b)const{
return x<b.x||x==b.x&&y<b.y;
 }
 }dd[N],tt[N];
struct cod{
int l,r;
int num;
int cal;
}tree[3*N];
int n,m,flag[N],x,y;
bool cmp(const node a,const node b){
return a.id<b.id;
}
void build(int l,int r,int dep)
{
tree[dep].l=l;
tree[dep].r=r;
tree[dep].num=0;
tree[dep].cal=0;
if(l<r){
int mid=(l+r)/2;
build(l,mid,2*dep);
build(mid+1,r,2*dep+1);
}
}
void add(int l,int r,int val,int dep)
{
if(l<=tree[dep].l&&tree[dep].r<=r){
tree[dep].cal=val;
tree[dep].num=dd[val].y;
return;
}
int mid=(tree[dep].l+tree[dep].r)/2;
if(mid>=l) add(l,r,val,2*dep);
if(mid<r) add(l,r,val,2*dep+1);
tree[dep].num=max(tree[2*dep].num,tree[2*dep+1].num);
}
void remove(int l,int r,int val,int dep)
{
if(l<=tree[dep].l&&tree[dep].r<=r){
tree[dep].num=0;
tree[dep].cal=0;
return;
}
int mid=(tree[dep].l+tree[dep].r)/2;
if(mid>=l) remove(l,r,val,2*dep);
if(mid<r) remove(l,r,val,2*dep+1);
tree[dep].num=max(tree[2*dep].num,tree[2*dep+1].num);
}
bool find(int l,int r,int val,int dep)
{
int mx=tree[dep].num;
if(mx<=dd[val].y) return false;
if(tree[dep].l==tree[dep].r){
int id=tree[dep].cal;
if(id!=0){
if(dd[id].x>dd[val].x&&dd[id].y>dd[val].y){
x=dd[id].x,y=dd[id].y;
return true;
}
}
return false;
}
int mid=(tree[dep].l+tree[dep].r)/2;
if(mid>=l){
if(find(l,r,val,2*dep)) return true;
}
if(mid<r){
if(find(l,r,val,2*dep+1)) return true;
}
return false;
}
void solve()
{
int cnt=1;
while(scanf("%d",&n)&&n){
build(1,n,1);
m=0;
for(int i=1;i<=n;i++){
scanf("%s%d%d",dd[i].s,&dd[i].x,&dd[i].y);
dd[i].id=i;
}
sort(dd+1,dd+n+1);
for(int i=1;i<=n;i++){
if(i>1){
if(dd[i].x==dd[i-1].x&&dd[i].y==dd[i-1].y){
flag[dd[i].id]=flag[dd[i-1].id];
}
else flag[dd[i].id]=++m;
}
else flag[dd[i].id]=++m;
}
sort(dd+1,dd+n+1,cmp);
if(cnt>1) printf("\n");
printf("Case %d:\n",cnt++);
for(int i=1;i<=n;i++){
if('a'==dd[i].s[0]){
add(flag[i],flag[i],i,1);
}
else if('r'==dd[i].s[0]){
remove(flag[i],flag[i],i,1);
}
else{
x=-N,y=-N;
find(flag[i],m,i,1);
if(x!=-N)
printf("%d %d\n",x,y);
else printf("-1\n");
}
}
}
}
int main()
{
solve();
return 0;
}
|