首页 > 代码库 > ACM基础训练题解4301 城市地平线
ACM基础训练题解4301 城市地平线
遍历线段树 线段树的插入和查询
1 //城市地平线(线段树) 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 #include<cstdio> 7 using namespace std; 8 typedef __int64 LL; 9 struct building{10 LL x1;11 LL x2;12 LL height;13 }line[50000];14 LL node[100000];15 struct tree{16 LL left;17 LL right;18 LL hi;19 }treenode[1000000];20 bool cmp(building a,building b){21 return (a.height<b.height );22 }23 void clear(int n){24 memset(treenode,0,sizeof(treenode));25 memset(node,0,sizeof(node));26 memset(line,0,sizeof(line));27 for(int i=1;i<=n;i++){28 cin>>line[i].x1>>line[i].x2>>line[i].height;29 node[i*2-1]=line[i].x1;30 node[i*2]=line[i].x2;31 }32 sort(line+1,line+n+1,cmp);33 int j=1;34 sort(node+1,node+1+2*n);35 for(int i=1;i<=n*2;i++){36 if(node[j]!=node[i])37 node[++j]=node[i];38 }39 node[0]=j;40 return ;41 }42 void creatree(int ll,int rr,int p){43 treenode[p].left=node[ll];44 treenode[p].right=node[rr];45 if(ll+1==rr)46 return ;47 int mid=(ll+rr)/2;48 creatree(ll,mid,p*2);49 creatree(mid,rr,p*2+1);//***50 return ;51 }52 void insert(LL ileft,LL iright,LL value,int p){53 if(ileft<=treenode[p].left && treenode[p].right<=iright){54 treenode[p].hi=value;55 return ;56 }57 if(treenode[p].hi>0)58 treenode[p*2].hi=treenode[p*2+1].hi=treenode[p].hi;59 treenode[p].hi=-1;60 if(iright>treenode[p*2].right)61 insert(ileft,iright,value,p*2+1);62 if(ileft<treenode[p*2].right)63 insert(ileft,iright,value,p*2);64 return ;65 }66 LL search(int p){67 if(treenode[p].hi>0)68 return (treenode[p].hi*(treenode[p].right-treenode[p].left));69 if(treenode[p].hi==0)70 return 0;71 return (search(p*2)+search(p*2+1));72 }73 int main(){74 int n;75 cin>>n;76 clear(n);77 creatree(1,node[0],1);78 for(int i=1;i<=n;i++)79 insert(line[i].x1,line[i].x2,line[i].height,1);80 cout<<search(1)<<endl;81 return 0;82 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。