先看看上一个题：
题目大意是： 矩阵中有N个被标记的元素，然后针对每一个被标记的元素e（x，y），你要在所有被标记的元素中找到一个元素E（X，Y），使得X>x并且Y>y，如果存在多个满足条件的元素，先比较X，选择X最小的那个，如果还是有很多满足条件的元素，再比较Y，选择Y最小的元素，如果不存在就输出两个-1；
分析： 直接暴力就行了
这个题目大意：
这个题是上个题的坚强版，每次会增加或减少一个点，仍然找到一个元素E（X，Y），使得X>x并且Y>y；
最多有200000次操作，每次只能是O(logn)的查询，行有1000000000之大，但是最多只会出现200000个不同的行，所以要离散化一下。然后对于每行的所有列用set去存，用线段树来维护每一行的出现的最大列，具体看代码吧
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#define MAXN 200010 using namespace std; int Max[MAXN<<], b[MAXN], c[MAXN], cnt;
set<int>sy[MAXN];
struct node
{
int x, y, flag;
} n[];
void PushUp(int root)
{
Max[root]=max(Max[root*],Max[root*+]);
}
void Update(int p, int x, int L, int R, int root) //a[p]=x,并且更新最大值
{
if(L==R)
{
Max[root]=x;
return ;
}
int mid=(L+R)/;
if(p<=mid) Update(p,x,L,mid,root*);
else Update(p,x,mid+,R,root*+);
PushUp(root);
}
int Query(int num, int post_ll, int L, int R, int root)//从post_ll这个位置开始向右查找，返回大于等于num的位置下表
{
if(L==R)
{
if(Max[root]>=num) return L;
else return -;
}
int ans=-, mid=(L+R)/;
if(post_ll<=mid&&Max[root*]>=num) ans=Query(num,post_ll,L,mid,root*);
if(ans!=-) return ans;
if(Max[root*+]>=num) ans=Query(num,post_ll,mid+,R,root*+);
return ans;
} int BS1(int x)
{
int low=, high=cnt, mid;
while(low<=high)
{
mid=low+high>>;
if(c[mid]==x) return mid;
else if(c[mid]>x) high=mid-;
else low=mid+;
}
}
int BS2(int x)
{
int low=, high=cnt, mid, ans=-;
while(low<=high)
{
mid=low+high>>;
if(c[mid]>x)
{
ans=mid;
high=mid-;
}
else low=mid+;
}
return ans;
}
void init(int nn)
{
for(int i=; i<nn; i++)
sy[i].clear();
memset(Max,-,sizeof(Max));
}
int main()
{
int nn, x, tot, ans, cas=;
char cmd[];
while(scanf("%d",&nn)!=EOF&&nn)
{
cnt=tot=;
init(nn);
for(int i=; i<nn; i++)
{
scanf("%s%d%d",cmd,&n[i].x,&n[i].y);
if(!strcmp(cmd,"add"))
{
n[i].flag=;
b[tot++]=n[i].x;
}
else if(!strcmp(cmd,"find"))
n[i].flag=;
else n[i].flag=;
}
sort(b,b+tot);
c[]=b[];
for(int i=; i<tot; i++)
{
if(b[i]!=b[i-])
c[++cnt]=b[i];
}//离散化
printf("Case %d:\n",++cas);
for(int i=; i<nn; i++)
{
if(n[i].flag==)
{
x=BS1(n[i].x);
sy[x].insert(n[i].y);
Update(x,*(--sy[x].end()),,cnt,);
}
else if(n[i].flag==)
{
x=BS2(n[i].x);
if(x==-)
{
puts("-1");
continue ;
}
ans=Query(n[i].y+,x,,cnt,);
if(ans==-) printf("-1\n");
else printf("%d %d\n",c[ans],*(sy[ans].lower_bound(n[i].y+)));
}
else
{
x=BS1(n[i].x);
sy[x].erase(n[i].y);
if(!sy[x].size())
{
Update(x,-,,cnt,);
}
else Update(x,*(--sy[x].end()),,cnt,);
}
}
printf("\n");
}
return ;
}