Hdu1754IHateIt解题报告

《Hdu1754IHateIt解题报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Hdu1754IHateIt解题报告/*Name:hdu1754解题报告Copyright:ecjtu_acm训练基地Author:yimaoDate:03-08-1018:40Description:线段树，更新节点，区间求最值*/一、题目ProblemDescription很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。Input本题目包含多组测试，请处理到文件结束。在每个测试的第一行，有两个正整数N和M

2、(0

3、utput5659HintHugeinput,theCfunctionscanf()willworkbetterthancin二、题目大意及分析给定N个按一定顺序排列的值，对这N个值进行两种操作：1、查询某个区间[from,to]的最大值；2、修改序号为order处的值；分析：由于N很大，用一般的线性结构会超时，故选择用线段树做。此题可以直接套用线段树的三个模板，一个是建树的模板，另一个是求区间最大值的模板，还有一个是修改某个点的值的模板。三、部分源代码及相关分析/*2010-08-0310:08:28Accepted17541093MS9268K2183BG++*/structnod

4、e{intleft,mid,right,max;//mid不需要，下意识地写进去了；//线段树的节点保存所有信息，依题意要求具体加数据；//每个节点都是一个[a,b)的区间，根节点代表了整个所要处理的区间}T[600010];5//T[]数组大小一般是保存输入数据数组的大小的三倍，更小会Runtimeerror.//P.S.zhousc意见：写十万亦可，可能在建树的时候不会开到那么大，不一定非得三倍。//笔者试过几题，最好写三倍。//线段树把区间上的任意一条长度为L的线段都分成不超过2logL条线段的并；//建立一颗线段树，采用递归，线段树很多模板都采用递归；//第u个节点的最左端为l

5、，最右端为r，l，r是指保存输入数据的数组的下标；//结构体数组保存线段树，根节点下标为1。对于非叶节点num，其左右子节点下标分别为//2*num和2*num+1.(代码采用加法)，所以表示节点的结构体中不需要指向左右节点的量；voidcreate(intu,intl,intr){T[u].left=l;T[u].right=r;T[u].mid=(l+r)>>1;//P.S.mid并不需要；if(l==r){T[u].max=a[r];return;}intmid=(l+r)>>1;//位运算比除法快；create(u+u,l,mid);create(u+u+1,mid+1,r);

6、//加法比乘法快；T[u].max=max(T[u+u].max,T[u+u+1].max);}//查找区间[from,to]上的最大值；//主函数里i应该写1；intsearch_max(intfrom,intto,inti){if(from<=T[i].left&&to>=T[i].right){returnT[i].max;}else5{intans1=-20000000,ans2=-20000000;if(from<=T[i+i].right)ans1=search_max(from,to,i+i);if(to>=T[i+i+1].left)ans2=search_max(fr

7、om,to,i+i+1);returnmax(ans1,ans2);}}//改变输入的数据中序号为order的值为num，同时更新该树；voidchange_tree(intorder,intnum,inti){//if(order==T[i].left&&order==T[i].right)//{T[i].max=num;return;}if(T[i].left==T[i].right){T[i].max=num;return;}else{i