求条

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lson (id * 2)
#define rson (id * 2 + 1)
#define mid ((tree[id].l + tree[id].r) >> 1)
struct tree
{
	int l, r, max, maxh, reset, lazy, lazyh;
} tree[400005];
int n, q, a[100005];

void push_up(int id)
{
	tree[id].max = max(tree[lson].max, tree[rson].max);
	tree[id].maxh = max(tree[lson].maxh, tree[rson].maxh);
}

void push_down(int id)
{
	int L = tree[id].l, R = tree[id].r;
	if (tree[id].reset)
	{
		tree[lson].reset = tree[rson].reset = tree[id].reset;
		tree[lson].max = tree[id].reset;
		tree[rson].max = tree[id].reset;
		tree[lson].lazyh = max(tree[id].reset, tree[lson].lazyh);
		tree[rson].lazyh = max(tree[id].reset, tree[rson].lazyh);
		tree[lson].maxh = max(tree[lson].maxh, tree[id].reset);
		tree[rson].maxh = max(tree[rson].maxh, tree[id].reset);
		tree[id].reset = 0;
	}
	if (tree[id].lazy)
	{
		tree[lson].max = tree[lson].max + tree[id].lazy;
		tree[rson].max = tree[rson].max + tree[id].lazy;
		tree[lson].lazyh = max(tree[lson].max + tree[id].lazy, tree[lson].lazyh);
		tree[rson].lazyh = max(tree[rson].max + tree[id].lazy, tree[rson].lazyh);
		tree[lson].maxh = max(tree[lson].maxh, tree[lson].lazyh);
		tree[rson].maxh = max(tree[rson].maxh, tree[rson].lazyh);
		tree[lson].lazy += tree[id].lazy, tree[rson].lazy += tree[id].lazy;
		tree[id].lazy = 0;
	}
}

void build(int id, int l, int r)
{
	tree[id].l = l, tree[id].r = r;
	if (l == r)
	{
		tree[id].max = a[l];
		tree[id].maxh = a[l];
		return;
	}
	build(lson, l, mid), build(rson, mid + 1, r), push_up(id);
}

void change(int id, int l, int r, int k)
{
	int L = tree[id].l, R = tree[id].r;
	if (L >= l && R <= r)
	{
		tree[id].max = max(tree[id].max, tree[id].max + k);
		tree[id].lazy += k;
		tree[id].lazyh = max(tree[id].lazyh, tree[id].max + k);
		return;
	}
	push_down(id);
	if (l <= mid) change(lson, l, r, k);
	if (r >= mid + 1) change(rson, l, r, k);
	push_up(id);
}

void reset(int id, int l, int r, int k)
{
	int L = tree[id].l, R = tree[id].r;
	if (L >= l && R <= r)
	{
		tree[id].max = k, tree[id].maxh = max(tree[id].maxh, k), tree[id].reset = k;
		tree[id].lazy = 0;
		return;
	}
	push_down(id);
	if (l <= mid) reset(lson, l, r, k);
	if (r >= mid + 1) reset(rson, l, r, k);
	push_up(id);
}

int queryh(int id, int l, int r)
{
	int L = tree[id].l, R = tree[id].r;
	if (L >= l && R <= r)
	{
		return tree[id].maxh;
	}

	push_down(id);
	int res = -0x3f3f3f3f;
	if (l <= mid) res = max(res, queryh(lson, l, r));
	if (r >= mid + 1) res = max(res, queryh(rson, l, r));
	return res;
}

int query(int id, int l, int r)
{
	int L = tree[id].l, R = tree[id].r;
	if (L >= l && R <= r)
	{
		return tree[id].max;
	}

	push_down(id);
	int res = -0x3f3f3f3f;
	if (l <= mid) res = max(res, query(lson, l, r));
	if (r >= mid + 1) res = max(res, query(rson, l, r));
	return res;
}

signed main()
{
	scanf("%lld", &n);
	for (int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
	build(1, 1, n);
	scanf("%lld", &q);
	while (q --)
	{
		char op;
		int l, r, k;
		cin >> op >> l >> r;
		if (op == 'P') scanf("%lld", &k), change(1, l, r, k);
		else if (op == 'Q') printf("%lld\n", query(1, l, r));
		else if (op == 'A') printf("%lld\n", queryh(1, l, r));
		else scanf("%lld", &k), reset(1, l, r, k);
	}
	return 0;
}