hdu1754 I Hate It (线段树 更新点的值)

hdu1754 I Hate It (线段树 更新点的值)

I Hate It

Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 51089    Accepted Submission(s): 20037

Problem Description

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。 这让很多学生很反感。 不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input

本题目包含多组测试，请处理到文件结束。 在每个测试的第一行，有两个正整数 N 和 M ( 0

Output

对于每一次询问操作，在一行里面输出最高成绩。

Sample Input

5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5

Sample Output

Hint

Huge input,the C function scanf() will work better than cin

Author

linle

Source

Recommend

lcy   |   We have carefully selected several similar problems for you:   ​​1166​​​  ​​​1698​​​  ​​​1542​​​  ​​​1394​​​  ​​​2795​​

​​Statistic​​ |

​​Submit​​ |

​​Discuss​​ |

​​Note​​

看到那么多的查找次数用线段树无疑了。。

#include #include #include using namespace std;struct node{ int left,right,val;}c[200000*3];void build_tree(int l,int r,int root)//建树{ c[root].left=l; c[root].right=r; if(l==r) { scanf("%d",&c[root].val); return ; } int mid=(c[root].left+c[root].right)/2; build_tree(l,mid,root*2); build_tree(mid+1,r,root*2+1); c[root].val=max(c[root*2].val,c[root*2+1].val);}void search_tree(int l,int r,int root,int &Max)//查找{ if(c[root].left==l&&c[root].right==r) { Max=c[root].val; return ; } int mid=(c[root].left+c[root].right)/2; if(mid=r) search_tree(l,r,root*2,Max); else { int Max1; search_tree(l,mid,root*2,Max); search_tree(mid+1,r,root*2+1,Max1); Max=max(Max,Max1); }}void update_tree(int pos,int root,int x)//更新点{ if(c[root].left==c[root].right&&c[root].left==pos) { c[root].val=x; return ; } int mid=(c[root].left+c[root].right)/2; if(mid

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。