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 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
| #pragma GCC optimize(2) #pragma GCC optimize(3, "Ofast", "inline") #include<bits/stdc++.h> using namespace std;
#define int long long
typedef long long ll; typedef __int128 int128;
namespace FastIO { char buf[1 << 20], *p1, *p2; #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++) template<typename T> inline T read(T& x) { x = 0; int f = 1; char ch; while (!isdigit(ch = getchar())) if (ch == '-') f = -1; while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); x *= f; return x; } template<typename T, typename... Args> inline void read(T& x, Args &...x_) { read(x); read(x_...); return; } inline ll read() { ll x; read(x); return x; } }; using namespace FastIO;
const int N = 5e4 + 10;
struct Node { int L, R; ll ls, rs; ll sum, mi; Node() {} Node(int L, int R, ll ls, ll rs, ll sum, ll mi) : L(L), R(R), ls(ls), rs(rs), sum(sum), mi(mi) {} Node operator + (const Node& b) const { Node ans(min(L, b.L), max(R, b.R), -1e18, -1e18, sum + b.sum, -1e18); ans.ls = max(ls, b.ls + sum); ans.rs = max(b.rs, rs + b.sum); ans.mi = max(max(mi, b.mi), rs + b.ls); return ans; } }; class SegTree { private : Node node[N << 2]; public : void Build(int p, int L, int R, int *a) { node[p].L = L, node[p].R = R; if(L == R) { node[p].ls = node[p].rs = node[p].mi = node[p].sum = a[L]; return ; } int mid = L + R >> 1; Build(p << 1, L, mid, a); Build(p << 1 | 1, mid + 1, R, a); node[p] = node[p << 1] + node[p << 1 | 1]; } Node Query(int p, int L, int R) { if(L <= node[p].L && node[p].R <= R) { return node[p]; } int mid = node[p].L + node[p].R >> 1; Node ans(1e9, -1e9, -1e18, -1e18, 0, -1e18); if(L <= mid) ans = ans + Query(p << 1, L, R); if(mid < R) ans = ans + Query(p << 1 | 1, L, R); return ans; } };
int n, Q; int a[N];
SegTree tree;
inline void Input() { read(n); for(int i = 1; i <= n; i++) { read(a[i]); } read(Q); }
inline void Work() { tree.Build(1, 1, n, a); int l, r; while(Q--) { read(l, r); printf("%lld\n", tree.Query(1, l, r).mi); } }
signed main() { int T = 1; while(T--) { Input(); Work(); } return 0; }
|