HDU 4027 线段树

发布时间:2017-3-29 15:20:34 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 4027 线段树",主要涉及到HDU 4027 线段树方面的内容,对于HDU 4027 线段树感兴趣的同学可以参考一下。

核心思想: 任何64位以内的值,开根号最多不会超过7次。 对于成段数据,若全为1,则不再进行运算       #include "stdio.h" #include "string.h" #include "math.h" #include "stdlib.h" struct comp { int l,r,mid,x; __int64 n; } data[300001]; __int64 ans; void build(int l,int r,int k) { data[k].l=l; data[k].r=r; data[k].mid=(l+r)/2; data[k].x=0; // 记录此段数据是否全为1 if (l==r) { scanf("%I64d",&data[k].n); if (data[k].n==1) data[k].x=1; return ; } build(l,data[k].mid,2*k); build(data[k].mid+1,r,2*k+1); data[k].n=data[k*2].n+data[k*2+1].n; if (data[k*2].x==1 && data[k*2+1].x==1) data[k].x=1; } void update(int l,int r,int k) { if (data[k].x==1) return ; // 若此段全为1,则不再运算,核心思想 if (data[k].l==l && data[k].r==r && r==l) { data[k].n=(__int64 )sqrt( (double) data[k].n); if (data[k].n==1) data[k].x=1; return ; } if (r<=data[k].mid) update(l,r,k*2); else if (l>data[k].mid) update(l,r,k*2+1); else { update(l,data[k].mid,k*2); update(data[k].mid+1,r,k*2+1); } data[k].n=data[k*2].n+data[k*2+1].n; if (data[k*2].x==1 && data[k*2+1].x==1) data[k].x=1; } void search(int l,int r,int k) { if (l==data[k].l && r==data[k].r) { ans+=data[k].n; return ; } if (r<=data[k].mid) search(l,r,k*2); else if (l>data[k].mid) search(l,r,k*2+1); else { search(l,data[k].mid,k*2); search(data[k].mid+1,r,k*2+1); } } int main() { int temp,t,n,a,b,c,m; t=0; while (scanf("%d",&n)!=EOF) { t++; build(1,n,1); scanf("%d",&m); printf("Case #%d:\n",t); while (m--) { scanf("%d%d%d",&a,&b,&c); if (b>c) { temp=b; b=c; c=temp; } if (a==0) update(b,c,1); else { ans=0; search(b,c,1); printf("%I64d\n",ans); // 注意要开INT64,否则WA } } printf("\n"); } return 0; }  

上一篇:【Unity插件】LitJson杂谈
下一篇:JavaSe 3. java常用类库,包介绍及开发工具

相关文章

关键词: HDU 4027 线段树

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款