P4513求调

9pts 对了第一个点

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct park
{
	int maxl , maxr;
	int maxn;
	int sum;
	int l , r;
}tree[500005 * 4];
int a[500005];
park operator+(park L , park R)
{
	park x;
	x.l = L.l;
	x.r = R.r;
	x.maxn = max(L.maxr + R.maxl , max(L.maxn , R.maxn));
	x.maxl = max(L.maxl , L.sum + R.maxl);
	x.maxr = max(R.maxr , R.sum + L.maxr);
	x.sum = L.sum + R.sum;
	return x;
}
void pushUP(int x)
{
	tree[x] = tree[x * 2] + tree[x * 2 + 1];
}
void build(int x , int lc , int rc)
{
	tree[x].l = lc;
	tree[x].r = rc;
	if(lc == rc)
	{
		tree[x].maxl = tree[x].maxr;
		tree[x].maxn = tree[x].sum = a[lc];
		return ;
	}
	int m = (lc + rc) / 2;
	build(x * 2 , lc , m);
	build(x * 2 + 1 , m + 1 , rc);
	pushUP(x);
}
park query(int x , int lc , int rc)
{
	if(lc <= tree[x].l && tree[x].r <= rc)
	{
		return tree[x];
	}
	int m = (tree[x].l + tree[x].r) / 2;
	if(rc <= m)
	{
		return query(x * 2 , lc , rc);
	}
	if(m < lc)
	{
		return query(x * 2 + 1 , lc , rc);
	}
	return query(x * 2 , lc , rc) + query(x * 2 + 1 , lc , rc);
}
void modify(int x , int p , int s)
{
	if(tree[x].l == tree[x].r)
	{
		tree[x].maxl = tree[x].maxr = s;
		tree[x].maxn = tree[x].sum = s;
		return ;
	}
	int m = (tree[x].l + tree[x].r) / 2;
	if(p <= m)
	{
		modify(x * 2 , p , s);
	}
	else
	{
		modify(x * 2 + 1 , p , s);
	}
	pushUP(x);
}
int n , m , p , x , y;
signed main()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
	}
	build(1 , 1 , n);
	while(m--)
	{
		cin >> p >> x >> y;
		if(p == 1)
		{
			if(x > y)
			{
				swap(x , y);
			}
			cout << query(1 , x , y).maxn << endl;
		}
		else
		{
			modify(1 , x , y);
		}
	}
	return 0;
}