2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛 L 捡贝壳

题目链接

还没补

一道类似的题
线段树上维护四个信息，从左端点向右连续的最大值lmx，从右端点向左连续的做大值rmx，区间最大值mx，区间和sum，每次pushup的时候如何维护四个信息？
对于lmx更新的时候需要用左儿子的lmx和左儿子的和加上右儿子的lmx取max
对于rmx更新的时候需要用右儿子的rmx和右儿子的和加上左儿子的rmx取max
对于sum直接左右儿子加起来即可
对于区间最值，在左儿子的mx和右儿子的mx和左儿子的rmx加上右儿子的lmx取max

#include <iostream>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <queue>
#include <numeric>
#include <cassert>
#include <bitset>
#include <cstdio>
#include <vector>
#include <unordered_set>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <tuple>
#include <array>
 
#define all(a) a.begin(), a.end()
#define cnt0(x) __builtin_ctz(x)
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define cntone(x) __builtin_popcount(x)
#define db double
#define fs first
#define se second
#define AC main(void)
#define HYS std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
typedef std::pair<int, int > PII;
typedef std::pair<int, std::pair<int, int>> PIII;
typedef std::pair<ll, ll> Pll;
typedef std::pair<double, double> PDD;
using ld = double long;

const long double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 10, M = 4e5 + 10;
int n , m, p;

int d1[] = {0, 0, 1, -1};
int d2[] = {1, -1, 0, 0};

int a[N];

struct node{
	int l, r;
	ll lmx, rmx, sum, mx;
}tr[N << 2];

inline void pushup(node &u,node &l,node &r){
    u.sum = l.sum + r.sum;
    u.lmx = std::max(l.lmx, l.sum + r.lmx);
    u.rmx = std::max(r.rmx, r.sum + l.rmx);
    u.mx = std::max({l.mx, r.mx, l.rmx + r.lmx});
}

inline void pushup(int u){
	pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

inline void build_tree(int u, int l, int r){
	tr[u] = {l, r};
	if(l == r){
		tr[u].lmx = tr[u].rmx = tr[u].mx = tr[u].sum = a[l];
		return ;
	}
	
	int mid = l + r >> 1;
	build_tree(u << 1, l, mid);
	build_tree(u << 1 | 1, mid + 1, r);
	pushup(u);
}

inline void modify(int u, int x, int v){
	if(tr[u].l == tr[u].r){
		tr[u].sum = tr[u].lmx = tr[u].rmx = tr[u].mx = v;
		return ;
	}
	
	int mid = tr[u].l + tr[u].r >> 1;
	if(x <= mid)	modify(u << 1, x, v);
	else modify(u << 1 | 1, x, v);
	pushup(u);
}

inline node query(int u, int l, int r){
	if(tr[u].l >= l && tr[u].r <= r)	return tr[u];
	int mid = tr[u].l + tr[u].r >> 1;
	if(r <= mid)	return query(u << 1, l, r);
	if(l > mid)	return query(u << 1 | 1, l ,r);
	node res;
	node ls = query(u << 1, l, r);
	node rs = query(u << 1 | 1, l, r);
	pushup(res, ls, rs);	

	return res;
}

inline void solve(){
	std::cin >> n >> m;
	for(int i = 1; i <= n; i ++)	std::cin >> a[i];
	build_tree(1, 1, n);
	while(m --){
		int op, l, r;
		std::cin >> op >> l >> r;
		if(op == 1){
			if(l > r)	std::swap(l, r);
			std::cout << query(1, l, r).mx << '\n';
		}	
		else modify(1, l, r);
	}
}

signed AC{
   	HYS
   	
	int _ = 1;
	//std::cin >> _;
	while(_ --)
        solve();

    return 0;
}