poj-3277-City Horizon-离散化+线段树区域更新

先把坐标离散化，然后进行线段树区域更新。

更新的时候应该注意先更新矮的，然后让高的覆盖矮的。

时间复杂度为O（n*log（n））

注意long long

注意线段树的空间长度应该开为maxn*2*4

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #define INF 1000000 #define LL long long #define maxn 80200 using namespace std; struct list { int l; int r; int h; }node[maxn*4+10]; struct lose { int x; int y; int h; bool friend operator < (const lose a, const lose b) { return a.h
        
         x)r=mid; if(xx[mid]
         
          mid )insert(l,r,h,num*2+2); else if(r<=mid)insert(l,r,h,num*2+1); else { insert(l,mid,h,num*2+1); insert(mid+1,r,h,num*2+2); } } int search(int x,int num) { int a=node[num].l; int b=node[num].r; int mid=(a+b)/2; if(node[num].h!=0)return node[num].h; if(a==b) { return 0; } if(x<=mid)return search(x,num*2+1); else return search(x,num*2+2); } int main() { int n; while(~scanf("%d",&n)) { for(int i=0;i