LG4513. 小白逛公园

题意描述

source: https://www.luogu.com.cn/problem/P4513

维护一个序列，支持两种操作：

• 单点修改
• 区间最大子段和

区间长度 $\in[1,500000]$，操作次数 $\in[1,100000]$，值域是 $[-1000,1000]$。

思路

维护区间和、区间最大前缀和、区间最大后缀和、区间最大子段和。这样很容易合并（详见 pushup 函数），也很容易查询（查询的时候返回一个包含上述四个信息的 std::tuple<int, int, int, int> 四元组，合并类似 pushup，详见代码 68 行）。

代码

source: https://www.luogu.com.cn/record/46114702

#define FILE_IO

#include <cstdio>
#include <algorithm>
#include <tuple>

namespace hermione {

int scan();
template <typename Type, typename... Args> int read(Type&, Args&...);
int token(char*);
template <typename Type> int lread(Type*, const int&);
template <typename Type, typename... Args> void print(const Type&, const Args&...);
template <typename Type> void lprint(Type* arr, const int& length);
#define debug(var) (print(#var, " = ", var, '\n'))
#define lineno() (print("line ", __LINE__, '\n'))

constexpr int MAXN = 500005;

struct node {
  int l, r;
  int ans, maxpre, maxsuf, sum;
} tree[MAXN * 4];
int a[MAXN];

void pushup(int root) {
  tree[root].sum = tree[root * 2].sum + tree[root * 2 + 1].sum;
  tree[root].maxpre = std::max(tree[root * 2].maxpre, tree[root * 2].sum + tree[root * 2 + 1].maxpre);
  tree[root].maxsuf = std::max(tree[root * 2 + 1].maxsuf, tree[root * 2 + 1].sum + tree[root * 2].maxsuf);
  tree[root].ans = std::max({tree[root * 2].ans, tree[root * 2 + 1].ans, tree[root * 2].maxsuf + tree[root * 2 + 1].maxpre});
}

void build(int root, int l, int r) {
  tree[root] = {l, r};
  if (l == r) {
    tree[root] = {l, r, a[l], a[l], a[l], a[l]};
    return;
  }
  int mid = (l + r) / 2;
  build(root * 2, l, mid);
  build(root * 2 + 1, mid + 1, r);
  pushup(root);
}

void modify(int root, int q, int val) {
  int l = tree[root].l, r = tree[root].r;
  if (q < l || r < q) { return; }
  if (l == r) {
    tree[root] = {l, r, val, val, val, val};
    return;
  }
  modify(root * 2, q, val);
  modify(root * 2 + 1, q, val);
  pushup(root);
}

std::tuple<int, int, int, int> query(int root, int ql, int qr) {
  int l = tree[root].l, r = tree[root].r;
  int mid = (l + r) / 2;
  if (ql <= l && r <= qr) {
    return {tree[root].ans, tree[root].maxpre, tree[root].maxsuf, tree[root].sum};
  } else if (qr <= mid) {
    return query(root * 2, ql, qr);
  } else if (ql > mid) {
    return query(root * 2 + 1, ql, qr);
  } else {
    auto x = query(root * 2, ql, qr), y = query(root * 2 + 1, ql, qr);
    return {std::max({std::get<0>(x), std::get<0>(y), std::get<2>(x) + std::get<1>(y)}), std::max(std::get<1>(x), std::get<3>(x) + std::get<1>(y)), std::max(std::get<2>(y), std::get<3>(y) + std::get<2>(x)), std::get<3>(x) + std::get<3>(y)};  
  }
}

int main(int argc, char** argv) {
  int n, m;
  read(n, m);
  lread(a + 1, n);
  build(1, 1, n);
  for (int i = 0; i < m; ++i) {
    int op = scan();
    if (op == 1) {
      int l, r;
      read(l, r);
      if (l > r) { l ^= r ^= l ^= r; }
      print(std::get<0>(query(1, l, r)), '\n');
    } else {
      int q, s;
      read(q, s);
      modify(1, q, s);
    }
  }
  return 0;
}

#ifndef TYPE_LESS_IO_
#define TYPE_LESS_IO_

#define mread(format) return std::scanf("%" format, &x)

int read(char& x) {
  return std::scanf(" %c", &x);
}
int read(unsigned char& x) {
  mread("hhu");
}
int read(short& x) {
  mread("hd");
}
int read(unsigned short& x) {
  mread("hu");
}
int read(int& x) {
  mread("d");
}
int read(unsigned int& x) {
  mread("u");
}
int read(long& x) {
  mread("ld");
}
int read(unsigned long& x) {
  mread("lu");
}
int read(long long& x) {
  mread("lld");
}
int read(unsigned long long& x) {
  mread("llu");
}
int read(float& x) {
  mread("f");
}
int read(double& x) {
  mread("lf");
}
int read(long double& x) {
  mread("Lf");
}
int read(void*& x) {
  mread("p");
}
int read(char* x) {
  return std::scanf(" %s", x);
}
int read() {
  return 0;
}

template <typename Type>
void read(const Type& x) {
  throw "read type error";
}

template <typename Type, typename... Args>
int read(Type& x, Args&... args) {
  return read(x) != EOF ? read(args...) : EOF;
}

int token(char* x) {
  return std::scanf("%s", x);
}

template <typename Type>
int lread(Type* arr, const int& length) {
  int ret = 0;
  for (int i = 0; i < length; ++i) {
    ret = read(arr[i]);
  }
  return ret;
}

int scan() {
  int x;
  read(x);
  return x;
}

#define mprint(format) std::printf("%" format, x)

void print(const char& x) {
  mprint("c");
}
void print(char* x) {
  mprint("s");
}
void print(const char* x) {
  mprint("s");
}
void print(const unsigned char& x) {
  mprint("hhu");
}
void print(const short& x) {
  mprint("hd");
}
void print(const unsigned short& x) {
  mprint("hu");
}
void print(const int& x) {
  mprint("d");
}
void print(const unsigned int& x) {
  mprint("u");
}
void print(const long& x) {
  mprint("ld");
}
void print(const unsigned long& x) {
  mprint("lu");
}
void print(const long long& x) {
  mprint("lld");
}
void print(const unsigned long long& x) {
  mprint("llu");
}
void print(const double& x) {
  mprint("le");
}
void print(const long double& x) {
  mprint("Le");
}
void print(void* x) {
  mprint("p");
}
void print() {}

template <typename Type>
void print(const Type& x) {
  throw "print type error";
}

template <typename Type, typename... Args>
void print(const Type& x, const Args&... args) {
  print(x);
  print(args...);
}

template <typename Type>
void lprint(Type* arr, const int& length) {
  for (int i = 0; i < length; ++i) {
    print(arr[i]);
    print(i == length - 1 ? '\n' : ' ');
  }
}
void lprint(char* arr, const int& length) {
  for (int i = 0; i < length; ++i) {
    print(arr[i]);
  }
  print('\n');
}

class typeof_print_LF_before_EOF {
public:
  ~typeof_print_LF_before_EOF() {
    print('\n');
  }
} print_LF_before_EOF;

#endif // ifndef TYPE_LESS_IO_

} // namespace hermione

int main(int argc, char** argv) {
  #if defined(DEBUG) && defined(FILE_IO)
  (std::freopen("test.in", "r", stdin));
  (std::freopen("test.out", "w", stdout));
  #endif
  int ret = hermione::main(argc, argv);
  #if defined(DEBUG) && defined(FILE_IO)
  (std::fclose(stdin));
  (std::fclose(stdout));
  #endif
  return ret;
}