题目地址：SDUT 2159 这题的数据很水。。几乎所有人都是水过去的。。网上也没找到正解，全是水过去的。于是我来第一发正解23333。 首先，可以想到的是先离线下来，然后对行离散化，然后对于每行的所有列用set去存，那么怎么去找最小的行有大于给出列的列数呢？这时候线段树就可以登场了，用线段树来维护每一行的出现的最大列，，这样就可以用线段树去搜了。然后删除添加操作同时在set与线段树中完成。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=200000+10;Max[MAXN<<2], b[MAXN], c[MAXN], cnt;set<int>st[MAXN];struct node{int x, y, z;}fei[300000];void PushUp(int rt){Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);}void Update(int p, int x, int l, int r, int rt){if(l==r){Max[rt]=x;return ;}int mid=l+r>>1;if(p<=mid) Update(p,x,lson);else Update(p,x,rson);PushUp(rt);}int Query(int x, int ll, int l, int r, int rt){if(l==r){if(Max[rt]>=x) return l;else return -1;}int ans=-1, mid=l+r>>1;if(ll<=mid&&Max[rt<<1]>=x) ans=Query(x,ll,lson);if(ans!=-1) return ans;if(Max[rt<<1|1]>=x) ans=Query(x,ll,rson);return ans;}int BS(int x){int low=0, high=cnt, mid;while(low<=high){mid=low+high>>1;if(c[mid]==x) return mid;else if(c[mid]>x) high=mid-1;else low=mid+1;}}int BS1(int x){int low=0, high=cnt, mid, ans=-1;while(low<=high){mid=low+high>>1;if(c[mid]>x) {ans=mid;high=mid-1;}else low=mid+1;}return ans;}void init(int n){for(int i=0;i<n;i++){st[i].clear();}memset(Max,-1,sizeof(Max));}int main(){int n, i, j, x, tot, ans, Case=0;char s[20];while(scanf(“%d”,&n)!=EOF&&n){cnt=tot=0;init(n);for(i=0;i<n;i++){scanf(“%s%d%d”,s,&fei[i].x,&fei[i].y);if(!strcmp(s,”add”)){fei[i].z=1;b[tot++]=fei[i].x;}else if(!strcmp(s,”find”)){fei[i].z=2;}else fei[i].z=3;}sort(b,b+tot);c[0]=b[0];for(i=1;i<tot;i++){if(b[i]!=b[i-1])c[++cnt]=b[i];}printf(“Case %d:\n”,++Case);for(i=0;i<n;i++){if(fei[i].z==1){x=BS(fei[i].x);st[x].insert(fei[i].y);Update(x,*(–st[x].end()),root);}else if(fei[i].z==2){x=BS1(fei[i].x);if(x==-1) {puts(“-1”);continue ;}ans=Query(fei[i].y+1,x,root);if(ans==-1) puts(“-1”);else printf(“%d %d\n”,c[ans],*(st[ans].lower_bound(fei[i].y+1)));}else{x=BS(fei[i].x);st[x].erase(fei[i].y);if(!st[x].size()){Update(x,-1,root);}else Update(x,*(–st[x].end()),root);}}puts(“”);}return 0;}
每一个成功者都有一个开始。勇于开始，才能找到成功的路。
