@[肖皓](/space/show?uid=19645) 请问你是怎么得到60分的？说一下！谢谢！
by Deny_小田 @ 2016-09-03 11:10:07
代码就是贴的线段树模板
···cpp
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int size = 210005;
int people[size],tot = 0;
struct _node{
int a,b,sum;
}t[size*4];
void build(int x, int y, int num){
t[num].a = x; t[num].b = y;
if(x == y) t[num].sum = people[y]; //如果到了叶子节点，就return
else{ //否则就继续建树
build(x, (x+y)/2, num*2); //左边
build((x+y)/2+1, y, num*2+1); //右边
t[num].sum = max(t[num*2].sum, t[num*2+1].sum); //当前树的 sum 就是两棵字数的 sum 的最大值
}
}
void change(int i, int j, int num){
t[num].sum = max(t[num].sum, j);
if(t[num].a == i&&t[num].a == t[num].b) return ;
if(i > (t[num].a+t[num].b)/2) change(i, j, num*2+1);
else change(i, j, num*2);
}
void query(int i, int j, int num){
if(i <= t[num].a&&j >= t[num].b){ tot = max(tot, t[num].sum); return ; }
int mid = (t[num].a+t[num].b)/2;
if(j <= mid) query(i, j, num*2);
else if(i > mid) query(i, j, num*2+1);
else{
query(i, j, num*2);
query(i, j, num*2+1);
}
}
int main(int argc, char const *argv[]){
int n,m;
while(scanf("%d %d",&n,&m)){
for(int i = 1; i <= n; i++) scanf("%d",&people[i]);
getchar();
build(1, n, 1);
while(m--){
char c;
int a,b;
scanf("%c %d %d",&c,&a,&b); getchar();
if(c == 'Q'){
tot = -2147483647;
query(a, b, 1);
printf("%d\n",tot);
}else if(c == 'U') change(a, b, 1);
}
}
return 0;
}
···
```
by Deny_小田 @ 2016-09-03 11:11:19
显然这有多组数据
by Drinkwater @ 2016-09-05 19:05:18
```cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
const long long maxn=2000000+10;
long long a[maxn],tree[maxn*4];
void build(int h,int l,int r){
if(l==r){tree[h]=a[l];return;}
int mid=l+r>>1;
build(h<<1,l,mid);
build(h<<1|1,mid+1,r);
tree[h]=max(tree[h<<1],tree[h<<1|1]);
}
int query_max(int h,int l,int r,int x,int y){
if(l==x&&r==y)return tree[h];
int mid=l+r>>1;
if(y<=mid)return query_max(h<<1,l,mid,x,y);
else if(x>mid)return query_max(h<<1|1,mid+1,r,x,y);
else return max(query_max(h<<1,l,mid,x,mid),query_max(h<<1|1,mid+1,r,mid+1,y));
}
void update(int h,int l,int r,int x,int y){
if(l==r){tree[h]=y;return;}
int mid=l+r>>1;
if(x<=mid)update(h<<1,l,mid,x,y);
else update(h<<1|1,mid+1,r,x,y);
tree[h]=max(tree[h<<1],tree[h<<1|1]);
}
int main(){
int i,j,k,m,n;
while(scanf("%d%d",&n,&m)!=EOF){
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
build(1,1,n);
while(m--){
char c[2];
getchar();
int x,y;
scanf("%s%d%d",c,&x,&y);
if(c[0]=='Q'){
if(x > y){
int tem = x;
x = y;
y = tem;
}
printf("%d\n",query_max(1,1,n,x,y));
}
if(c[0]=='U')update(1,1,n,x,y);
}
}
return 0;
}
```
by Drinkwater @ 2016-09-05 19:06:20