線段樹 第二個題目，求 區間 最大值。。
[cpp]
//============================================================================
// Name : HH.cpp
// Author : lxw
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include<algorithm>
using namespace std;
#define lson u<<1
#define rson u<<1|1
const int maxn=200010;
int dat[maxn];
struct Node{
int lef,rig,score,Max;
}T[maxn<<2];
void Build(int u,int l,int r){
T[u].lef=l;
T[u].rig=r; www.2cto.com
if(l==r){T[u].Max=T[u].score=dat[l];return;}
int mid=(l+r)>>1;
Build(lson,l,mid);
Build(rson,mid+1,r);
T[u].Max=max(T[lson].Max,T[rson].Max);
}
void Update(int u,int index,int val){
if(T[u].lef==index&&T[u].rig==index){T[u].Max=T[u].score=val;return;}
else {
if(index<=T[lson].rig)Update(lson,index,val);
else Update(rson,index,val);
T[u].Max=max(T[lson].Max,T[rson].Max);
}
}
int Query(int u,int from,int to){
if(T[u].lef==from&&T[u].rig==to){return T[u].Max;}
if(to<=T[lson].rig)return Query(lson,from,to);
if(from>=T[rson].lef)return Query(rson,from,to);
return max(Query(lson,from,T[lson].rig),Query(rson,T[rson].lef,to));
}
int main() {
int m,n;
char cmd;
int a,b;
while(scanf("%d%d",&n,&m)==2){
for(int i=1;i<=n;i++)scanf("%d",&dat[i]);
Build(1,1,n);
while(m--){
scanf(" %c%d%d",&cmd,&a,&b);
if(cmd=='U')Update(1,a,b);
else {
int ans=Query(1,a,b);
printf("%d\n",ans);
}
}
}
return 0;
}
作者:qingniaofy
