sdut 2159 Ivan comes again!(2010年山东省第一届ACM大学生程序设计竞赛) 线段树+离散

先看看上一个题：

题目大意是： 矩阵中有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去存，用线段树来维护每一行的出现的最大列，具体看代码吧

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<set>
  7 #include<queue>
  8 #include<stack>
  9 #define MAXN 200010
 10 
 11 using namespace std;
 12 
 13 int Max[MAXN<<2], b[MAXN], c[MAXN], cnt;
 14 set<int>sy[MAXN];
 15 struct node
 16 {
 17     int x, y, flag;
 18 } n[300000];
 19 void PushUp(int root)
 20 {
 21     Max[root]=max(Max[root*2],Max[root*2+1]);
 22 }
 23 void Update(int p, int x, int L, int R, int root) //a[p]=x,并且更新最大值
 24 {
 25     if(L==R)
 26     {
 27         Max[root]=x;
 28         return ;
 29     }
 30     int mid=(L+R)/2;
 31     if(p<=mid) Update(p,x,L,mid,root*2);
 32     else Update(p,x,mid+1,R,root*2+1);
 33     PushUp(root);
 34 }
 35 int Query(int num, int post_ll, int L, int R, int root)//从post_ll这个位置开始向右查找，返回大于等于num的位置下表
 36 {
 37     if(L==R)
 38     {
 39         if(Max[root]>=num) return L;
 40         else return -1;
 41     }
 42     int ans=-1, mid=(L+R)/2;
 43     if(post_ll<=mid&&Max[root*2]>=num) ans=Query(num,post_ll,L,mid,root*2);
 44     if(ans!=-1) return ans;
 45     if(Max[root*2+1]>=num) ans=Query(num,post_ll,mid+1,R,root*2+1);
 46     return ans;
 47 }
 48 
 49 int BS1(int x)
 50 {
 51     int low=0, high=cnt, mid;
 52     while(low<=high)
 53     {
 54         mid=low+high>>1;
 55         if(c[mid]==x) return mid;
 56         else if(c[mid]>x) high=mid-1;
 57         else low=mid+1;
 58     }
 59 }
 60 int BS2(int x)
 61 {
 62     int low=0, high=cnt, mid, ans=-1;
 63     while(low<=high)
 64     {
 65         mid=low+high>>1;
 66         if(c[mid]>x)
 67         {
 68             ans=mid;
 69             high=mid-1;
 70         }
 71         else low=mid+1;
 72     }
 73     return ans;
 74 }
 75 void init(int nn)
 76 {
 77     for(int i=0; i<nn; i++)
 78         sy[i].clear();
 79     memset(Max,-1,sizeof(Max));
 80 }
 81 int main()
 82 {
 83     int nn, x, tot, ans, cas=0;
 84     char cmd[20];
 85     while(scanf("%d",&nn)!=EOF&&nn)
 86     {
 87         cnt=tot=0;
 88         init(nn);
 89         for(int i=0; i<nn; i++)
 90         {
 91             scanf("%s%d%d",cmd,&n[i].x,&n[i].y);
 92             if(!strcmp(cmd,"add"))
 93             {
 94                 n[i].flag=1;
 95                 b[tot++]=n[i].x;
 96             }
 97             else if(!strcmp(cmd,"find"))
 98                 n[i].flag=2;
 99             else n[i].flag=3;
100         }
101         sort(b,b+tot);
102         c[0]=b[0];
103         for(int i=1; i<tot; i++)
104         {
105             if(b[i]!=b[i-1])
106                 c[++cnt]=b[i];
107         }//离散化
108         printf("Case %d:
",++cas);
109         for(int i=0; i<nn; i++)
110         {
111             if(n[i].flag==1)
112             {
113                 x=BS1(n[i].x);
114                 sy[x].insert(n[i].y);
115                 Update(x,*(--sy[x].end()),0,cnt,1);
116             }
117             else if(n[i].flag==2)
118             {
119                 x=BS2(n[i].x);
120                 if(x==-1)
121                 {
122                     puts("-1");
123                     continue ;
124                 }
125                 ans=Query(n[i].y+1,x,0,cnt,1);
126                 if(ans==-1) printf("-1
");
127                 else printf("%d %d
",c[ans],*(sy[ans].lower_bound(n[i].y+1)));
128             }
129             else
130             {
131                 x=BS1(n[i].x);
132                 sy[x].erase(n[i].y);
133                 if(!sy[x].size())
134                 {
135                     Update(x,-1,0,cnt,1);
136                 }
137                 else Update(x,*(--sy[x].end()),0,cnt,1);
138             }
139         }
140         printf("
");
141     }
142     return 0;
143 }