不过样例求条

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146#include<bits/stdc++.h>
#define endl '\n'
// #define MSOD

using namespace std;
using ll = long long;

constexpr ll N = 1e5 + 5, INF = 1e13;

struct MXT {
	int n, m;
	ll a[3][3];
	inline friend MXT operator * (MXT x, MXT y) {
		MXT res;
		res.n = x.n, res.m = y.m;
		for(int i = 0 ; i < x.n ; i ++) {
			for(int j = 0 ; j < y.m ; j ++) {
				res.a[i][j] = -INF;
				for(int k = 0 ; k < x.m ; k ++) {
					res.a[i][j] = max(res.a[i][j], x.a[i][k] + y.a[k][j]);
				}
			}
		}
		return res;
	}
	inline friend MXT operator + (MXT x, MXT y) {
		for(int i = 0 ; i < x.n ; i ++) {
			for(int j = 0 ; j < x.m ; j ++) {
				x.a[i][j] = max(x.a[i][j], y.a[i][j]);
			}
		}
		return x;
	}
} B1, B2;
int n;
ll b[N];
struct SGT {
	bool ok;
	MXT val, tg;
} t[N << 2];
#define ls (p << 1)
#define rs (p << 1 | 1)
inline void pushup(int p) {
	return t[p].val = t[ls].val + t[rs].val, void();
}
inline void lazy(int p, MXT d) {
	if(t[p].ok) {t[p].tg = t[p].tg * d;}
	else {t[p].tg = d;}
	t[p].val = t[p].val * d, t[p].ok = true;
	return;
}
inline void pushdown(int p) {
	if(t[p].ok) {
		t[p].ok = false;
		lazy(ls, t[p].tg), lazy(rs, t[p].tg);
	}
	return;
}
inline void build(int p, int pl, int pr) {
	t[p].ok = false, t[p].tg.n = t[p].tg.m = 3, t[p].val.n = 1, t[p].val.m = 3;
	if(pl == pr) {
		t[p].val.a[0][0] = b[pl], t[p].val.a[0][1] = b[pl], t[p].val.a[0][2] = 0;
	} else {
		int mid = (pl + pr) >> 1;
		build(ls, pl, mid);
		build(rs, mid + 1, pr);
		pushup(p);
	}
	return;
}
inline void upd(int p, int pl, int pr, int l, int r, MXT d) {
	if(l <= pl && pr <= r) {
		lazy(p, d);
	} else {
		int mid = (pl + pr) >> 1;
		pushdown(p);
		if(l <= mid) {
			upd(ls, pl, mid, l, r, d);
		}
		if(r > mid) {
			upd(rs, mid + 1, pr, l, r, d);
		}
		pushup(p);
	}
	return;
}
inline MXT qry(int p, int pl, int pr, int l, int r) {
	if(l <= pl && pr <= r) {
		return t[p].val;
	} else {
		int mid = (pl + pr) >> 1;
		pushdown(p);
		if(l <= mid && r > mid) {
			return (qry(ls, pl, mid, l, r) + qry(rs, mid + 1, pr, l, r));
		} else if(l <= mid) {
			return qry(ls, pl, mid, l, r);
		} else {
			return qry(rs, mid + 1, pr, l, r);
		}
	}
}
inline void solve()	{
	cin>>n;
	for(int i = 1 ; i <= n ; i ++) {
		cin>>b[i];
	}
	build(1, 1, n);
	B1.n = B1.m = B2.n = B2.m = 3;
	B1.a[0][0] = B1.a[0][1] = B1.a[0][2] = B1.a[1][0] = B1.a[1][2] = -INF;
	B2.a[0][2] = B2.a[1][0] = B2.a[1][2] = B2.a[2][0] = B2.a[2][1] = -INF;
	int q;
	cin>>q;
	while(q --) {
		int l, r;
		char op;
		cin>>op>>l>>r;
		if(op == 'Q') {
			cout<<qry(1, 1, n, l, r).a[0][0]<<endl;
		} else if(op == 'A') {
			cout<<qry(1, 1, n, l, r).a[1][0]<<endl;
		} else if(op == 'P') {
			ll z;
			cin>>z;
			B2.a[0][0] = B2.a[0][1] = z;
			upd(1, 1, n, l, r, B2);
		} else if(op == 'C') {
			ll z;
			cin>>z;
			B1.a[2][0] = B1.a[2][1] = z;
			upd(1, 1, n, l, r, B1);
		}
	}
	return;
}

signed main() {
	ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
	int TC = 1;
#ifdef MSOD
	cin>>TC;
#endif
	while(TC --) {
		solve();
	}
	return 0;
}