@[tuanzinb](/user/642504) maintain去掉就差不多了,另外tree中存的是最大值,不是和。三个点MLE,请大佬自行修改数据范围。
```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class SegTreeLazyRangeAddSet {
private:
vector<T> tree;
vector<T> *arr;
int n, root, n4, end;
T range_max(int l, int r, int cl, int cr, int p) {
if (l <= cl && cr <= r) return tree[p];
int m = cl + (cr - cl) / 2;
T mAx = -2147483648;
if (l <= m) mAx = max(mAx, range_max(l, r, cl, m, p * 2));
if (r > m) mAx = max(mAx, range_max(l, r, m + 1, cr, p * 2 + 1));
return mAx;
}
void range_set(int l, int r, T val, int cl, int cr, int p) {
if (l <= cl && cr <= r) {
tree[p] = max(tree[p], val);
return;
}
int m = cl + (cr - cl) / 2;
if (l <= m) range_set(l, r, val, cl, m, p * 2);
if (r > m) range_set(l, r, val, m + 1, cr, p * 2 + 1);
tree[p] = max(tree[p * 2], tree[p * 2 + 1]);
}
void build(int s, int t, int p) {
if (s == t) {
tree[p] = (*arr)[s];
return;
}
int m = s + (t - s) / 2;
build(s, m, p * 2);
build(m + 1, t, p * 2 + 1);
tree[p] = max(tree[p * 2], tree[p * 2 + 1]);
}
public:
explicit SegTreeLazyRangeAddSet<T>(vector<T> v) {
n = v.size();
n4 = n * 4;
tree = vector<T>(n4, 0);
arr = &v;
end = n - 1;
root = 1;
build(0, end, 1);
arr = nullptr;
}
T range_max(int l, int r) { return range_max(l, r, 0, end, root); }
void range_set(int l, int r, int val) { range_set(l, r, val, 0, end, root); }
};
int n,m,x,x1;
char o;
vector<int>a(100005);
SegTreeLazyRangeAddSet<int>st(a);
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>x;
st.range_set(i,i,x);
}
for(int i=1;i<=m;i++){
cin>>o>>x>>x1;
if(o=='Q'){
cout<<st.range_max(x,x1)<<endl;
}
if(o=='U'){
st.range_set(x,x,x1);
}
}
return 0;
}
```
by lujiayi654321 @ 2023-07-30 23:12:27
第$60$行改为$200005$就过了
by lujiayi654321 @ 2023-07-30 23:48:02