模板改自OI-WIKI的线段树模板

range_max区间最大

range_min区间最小

range_sum区间求和

range_set区间赋值

range_add区间加法

样例输出为9 6 9 15，错误

#include <bits/stdc++.h>
using namespace std;

template <typename T>
class SegTreeLazyRangeAddSet {
	private:
		vector<T> tree, lazy;
		vector<T> *arr;
		int n, root, n4, end;
		
		void maintain(int cl, int cr, int p) {
			int cm = cl + (cr - cl) / 2;
			if (cl != cr && lazy[p]) {
				lazy[p * 2] += lazy[p];
				lazy[p * 2 + 1] += lazy[p];
				tree[p * 2] += lazy[p] * (cm - cl + 1);
				tree[p * 2 + 1] += lazy[p] * (cr - cm);
				lazy[p] = 0;
			}
		}
		
		T range_sum(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 sum = 0;
			maintain(cl, cr, p);
			if (l <= m) sum += range_sum(l, r, cl, m, p * 2);
			if (r > m) sum += range_sum(l, r, m + 1, cr, p * 2 + 1);
			return sum;
		}
		
		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;
			maintain(cl, cr, p);
			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;
		}
	
		T range_min(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 mIn = 2147483647;
			maintain(cl, cr, p);
			if (l <= m) mIn = min(mIn, range_max(l, r, cl, m, p * 2));
			if (r > m) mIn = min(mIn, range_max(l, r, m + 1, cr, p * 2 + 1));
			return mIn;
		}
	
		void range_set(int l, int r, T val, int cl, int cr, int p) {
			if (l <= cl && cr <= r) {
				lazy[p] = val;
				tree[p] = (cr - cl + 1) * val;
				return;
			}
			int m = cl + (cr - cl) / 2;
			maintain(cl, cr, p);
			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] = tree[p * 2] + tree[p * 2 + 1];
		}
		
		void range_add(int l, int r, T val, int cl, int cr, int p) {
			if (l <= cl && cr <= r) {
				lazy[p] += val;
				tree[p] += (cr - cl + 1) * val;
				return;
			}
			int m = cl + (cr - cl) / 2;
			maintain(cl, cr, p);
			if (l <= m) range_add(l, r, val, cl, m, p * 2);
			if (r > m) range_add(l, r, val, m + 1, cr, p * 2 + 1);
			tree[p] = 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] = 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);
			lazy = vector<T>(n4, 0);
			arr = &v;
			end = n - 1;
			root = 1;
			build(0, end, 1);
			arr = nullptr;
		}
		
		void show(int p, int depth = 0) {
			if (p > n4 || tree[p] == 0) return;
			show(p * 2, depth + 1);
			for (int i = 0; i < depth; ++i) putchar('\t');
			printf("%d:%d\n", tree[p], lazy[p]);
			show(p * 2 + 1, depth + 1);
		}
		
		T range_sum(int l, int r) { return range_sum(l, r, 0, end, root); }
	
		T range_max(int l, int r) { return range_max(l, r, 0, end, root); }
	
		T range_min(int l, int r) { return range_min(l, r, 0, end ,root); }
	
	    void range_set(int l, int r, int val) { range_set(l, r, val, 0, end, root); }
		
		void range_add(int l, int r, int val) { range_add(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'){
			if(st.range_sum(x,x)<x1){
				st.range_set(x,x,x1);
			}
		}
	}
}