1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
| #include <bits/stdc++.h> using namespace std; using LL = long long; #define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i) #define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i) #ifdef zerol #define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0) #else #define dbg(...) #endif void err() { cout << "\033[39;0m" << endl; } template<template<typename...> class T, typename t, typename... Args> void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); } template<typename T, typename... Args> void err(T a, Args... args) { cout << a << ' '; err(args...); } // ----------------------------------------------------------------------------- const int N = 1E5 + 100; const LL inf = 1E10; LL a[N];
namespace Tree { #define lson o * 2, l, (l + r) / 2 #define rson o * 2 + 1, (l + r) / 2 + 1, r struct P { // max(? + x, y) LL x, y; } const E = {0, -inf}; P operator / (const P& a, const P& b) { return {max(-inf, a.x + b.x), max(a.y, a.x + b.y)}; } P Max(const P& a, const P& b) { return {max(a.x, b.x), max(a.y, b.y)}; } struct Node { P tag, htag; LL max, hmax; } t[N << 2]; void up(int o) { int lc = o * 2, rc = lc + 1; t[o].max = max(t[lc].max, t[rc].max); t[o].hmax = max(t[lc].hmax, t[rc].hmax); } void do_tag(int o, const Node& x) { t[o].htag = Max(t[o].htag, x.htag / t[o].tag); t[o].tag = x.tag / t[o].tag; t[o].hmax = max(t[o].hmax, max(t[o].max + x.htag.x, x.htag.y)); t[o].max = max(t[o].max + x.tag.x, x.tag.y); } void build(int o, int l, int r) { t[o].tag = t[o].htag = E; if (l == r) t[o].max = t[o].hmax = a[l]; else { build(lson); build(rson); up(o); } } void down(int o) { do_tag(o * 2, t[o]); do_tag(o * 2 + 1, t[o]); t[o].tag = t[o].htag = E; } void update(int ql, int qr, const P& x, int o, int l, int r) { if (r < ql || qr < l) return; if (ql <= l && r <= qr) { do_tag(o, {x, E, -1, -1}); return; } down(o); update(ql, qr, x, lson); update(ql, qr, x, rson); up(o); } LL query(int ql, int qr, int type, int o, int l, int r) { if (r < ql || qr < l) return -inf; if (ql <= l && r <= qr) return type ? t[o].hmax : t[o].max; down(o); return max(query(ql, qr, type, lson), query(ql, qr, type, rson)); } } using namespace Tree;
char s[10]; int main() { #ifdef zerol freopen("in", "r", stdin); #endif int n; cin >> n; FOR (i, 1, n + 1) scanf("%lld", &a[i]); build(1, 1, n); int Qn; cin >> Qn; while (Qn--) { int l, r; scanf("%s%d%d", s, &l, &r); if (s[0] == 'Q') printf("%lld\n", query(l, r, 0, 1, 1, n)); else if (s[0] == 'A') printf("%lld\n", query(l, r, 1, 1, 1, n)); else { int x; scanf("%d", &x); if (s[0] == 'P') update(l, r, {x, -inf}, 1, 1, n); else if (s[0] == 'C') update(l, r, {-inf, x}, 1, 1, n); } } }
|