5659
Hint
Huge input,the C function scanf() will work better than cin
题目链接：?pid=1754
解题思路：查询给出区间里的最值和更新值的问题，典型的线段树。
线段树重要的三个函数：1.Build(int left,int right,int rt)（建树），从根出发，每个节点表示一个区间，取区间中间值 mid = ( left + right ) >> 1，左右子节点的下标分别为 rt<<1 , rt<<1|1 , 区间分别为 [ left , mid ][mid+1,right]。
2.Qurey(int a,int b,int left,int right,int rt) ( 查询 )
3.Update(itn a,int b,int left,int right,int rt) (更新)
三个函数都用递归实现，，此题时间卡的特别紧，要用C写，用C++会超时。第一道线段树，参考了网上的题解。
代码如下：
#include <stdio.h>#include <string.h>#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define maxn 200010int n,m;int MAX[maxn<<2];int Max(int a,int b){return a>b?a:b;}void PushUp(int rt){MAX[rt]=Max(MAX[rt<<1],MAX[rt<<1|1]);}void Build(int l,int r,int rt){if(l==r) //叶子节点处输入权值；{scanf("%d",&MAX[rt]);return ;}int m=(l+r)>>1;Build(lson);Build(rson);PushUp(rt);//叶子节点处输入权值；}int Qurey(int a,int b,int l,int r,int rt) //查询区间a,b中的最大值{if(l>=a&&r<=b)// 区间[l,r]是区间[a,b]的子区间时，[l,r]里的最大值即为[a,b]里的最大值。return MAX[rt];int ret=0;int m=(r+l)>>1;if(a<=m)ret=Max(ret,Qurey(a,b,lson));if(b>m)ret=Max(ret,Qurey(a,b,rson));return ret;}void Update(int a,int b,int l,int r,int rt)//更新了一个值，整个线段树的权值都要更新{if(r==l) //当r==l 时找了该节点，按要求更改权值{MAX[rt]=b;return ;}int m=(r+l)>>1;if(a<=m)Update(a,b,lson);elseUpdate(a,b,rson);PushUp(rt); }int main(){int a,b;char c[2];while(scanf("%d%d",&n,&m)!=EOF){memset(MAX,0,sizeof(MAX));Build(1,n,1);while(m–){scanf("%s%d%d",c,&a,&b); //c定义为字符串形式代替getchar()if(c[0]=='Q')printf("%d\n", Qurey(a,b,1,n,1));elseUpdate(a,b,1,n,1);}}return 0;}
闽南的花市，一开始是来自漳州百花村，
