MLE 45 分 求助

// 单点修改，区间查询
#include <iostream>
#include <algorithm>
const int N = 5e5 + 10;
const int INF = -2e9;
typedef long long lint;

struct TreeNode {
  int l, r; // 区间为 [l,r]
  lint sum, ans, lmax, rmax;
  // sum：区间总和，ans：区间最大子段和，lmax：最大前缀，rmax：最大后缀
  TreeNode *lson, *rson;
  TreeNode(lint _sum = INF, lint _ans = INF, lint _lamx = INF, lint _rmax = INF, int _l = -1, int _r = -1, TreeNode *_lson = nullptr, TreeNode *_rson = nullptr)
  : l(_l), r(_r), sum(_sum), ans(_ans), lmax(_lamx), rmax(_rmax), lson(_lson), rson(_rson) {}
  ~TreeNode() {
    if (lson) delete lson;
    if (rson) delete rson;
    lson = rson = nullptr;
  }
};

int n, m, a[N];

bool inRange(TreeNode *u, int L, int R) { // 判断 [u->l,u->r] 是否被 [L,R] 完全包含
  return u->l >= L && u->r <= R;
}

bool outRange(TreeNode *u, int L, int R) { // 判断 [u->l,u->r] 是否与 [L,R] 完全无交
  return u->l > R || u->r < L;
}

void pushup(TreeNode *u, TreeNode *ls, TreeNode *rs) {
  u->sum = ls->sum + rs->sum;
  u->lmax = std::max(ls->lmax, ls->sum + rs->lmax);
  u->rmax = std::max(rs->rmax, rs->sum + ls->rmax);
  u->ans = std::max({ls->ans, rs->ans, ls->rmax + rs->lmax});
}

TreeNode *build(int l, int r) { // 建树
  TreeNode *u = new TreeNode;
  u->l = l, u->r = r;
  if (l == r) {
    u->sum = u->ans = u->lmax = u->rmax = a[l]; // 单个的所有值均为自身
    u->lson = u->rson = nullptr;
    return u;
  }
  int mid = l + r >> 1;
  u->lson = build(l, mid); // 左子树 [l,mid]
  u->rson = build(mid + 1, r); // 右子树 [mid + 1, r]
  pushup(u, u->lson, u->rson);
  return u;
}

TreeNode *query(TreeNode *u, int L, int R) {
  if (outRange(u, L, R)) return new TreeNode; // 默认 ans=INF 的值
  if (inRange(u, L, R)) return u;
  TreeNode *res = new TreeNode;
  pushup(res, query(u->lson, L, R), query(u->rson, L, R)); // 合并左右两棵子树查询得到的值
  return res;
}

void update(TreeNode *u, int p, int x) {
  if (u->l == u->r) {
    u->sum = u->ans = u->lmax = u->rmax = x;
    return ;
  }
  int mid = u->l + u->r >> 1;
  if (p <= mid) update(u->lson, p, x);
  else update(u->rson, p, x);
  pushup(u, u->lson, u->rson);
}

int main() {
  // freopen("sample.in", "r", stdin);
  // freopen("Std3.out", "w", stdout);
  std::cin.tie(0)->sync_with_stdio(0);
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  TreeNode *root = build(1, n);
  for (int k, a, b; m; --m) {
    std::cin >> k >> a >> b;
    int s = std::min(a, b), t = std::max(a, b);
    if (k == 1) std::cout << query(root, s, t)->ans << '\n';
    else update(root, a, b);
  }
  std::cout.flush();
  return 0;
}

记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)