我将你的数字又开大了 1 倍，60 变 90 且一个点 tle，线段树的左边界和右边界还是在递归里在线修改好，装成 struct 会慢很多 @[太阳之神2015](/space/show?uid=6851)
by Sooke @ 2017-10-26 21:56:56
@[Sooke](/space/show?uid=26673) 可是这个题解的代码过了
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=800000+2;
struct edge{
int l,r,mx;
}tree[MAXN];
int a[MAXN];
int n,m;
void buildtree(int x,int l,int r){
tree[x].l=l;
tree[x].r=r;
if(l==r){
tree[x].mx=a[l];
return;
}
buildtree(x*2,l,(l+r)>>1);
buildtree(x*2+1,1+((l+r)>>1),r);
tree[x].mx=max(tree[x*2].mx,tree[x*2+1].mx);
}
void update(int x,int l,int r,int k){
if(tree[x].l>=l && tree[x].r<=r){
tree[x].mx=max(tree[x].mx,k);
return;
}
if(tree[x].l>r || tree[x].r<l) return;
update(x*2,l,r,k);
update(x*2+1,l,r,k);
tree[x].mx=max(tree[x*2].mx,tree[x*2+1].mx);
}
int query(int x,int l,int r){
if(tree[x].l>=l && tree[x].r<=r) return tree[x].mx;
if(tree[x].l>r || tree[x].r<l) return 0;
int ans=0;
ans=max(query(2*x,l,r),query(2*x+1,l,r));
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
buildtree(1,1,n);
for(int i=1;i<=m;i++){
char pd;
int x,y;
cin>>pd;
if(pd=='Q'){
cin>>x>>y;
cout<<query(1,x,y)<<endl;
}
else{
cin>>x>>y;
update(1,x,x,y);
}
}
return 0;
}
```
by 太阳之神2015 @ 2017-10-27 21:01:34
@[太阳之神2015](/space/show?uid=6851)
区别在于位运算
× 2 可以写 << 1
× 2 + 1 可以写 << 1 | 1
可能是位运算挽回了很大的常数吧
by Sooke @ 2017-10-27 21:34:50