GSS1-Can you answer these queries I

Description

You are given a sequence \(a_1, a_2, \ldots, a_n\). (\(|a_i| \leq 15007, 1 \leq n \leq 50000\)) . A query is defined as follows:

\(Query(x, y) = max\{a_i + a_{i+1} + \ldots + a_j; x \leq i \leq j \leq y\}\).

Given \(m\) queries, your program must output the results of these queries.

Input

The first line of the input file contains the integer \(n\).

In the second line,\(n\) numbers follow.

The third line contains the integer \(m\).

\(m\) lines follow, where line \(i\) contains \(2\) numbers \(x_i\) and \(y_i\).

Output

Your program should output the results of the \(m\) queries, one query per line.

Sample Input

3
-1 2 3
1
1 2

Sample Output

2

Explanation

维护一棵线段树区间从左边开始的最大和和从右边开始的最大和和从中间开始的最大和. 这些数据可以 \(O(1)\) 合并, 于是就是一个不带修改的裸的区间线段树模板题.

比较好写, 可以一次 AC.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 50010;

struct interval {
    lli maxx, lmx, mmx, rmx, sum;
    interval(void) {
        maxx = lmx = mmx = rmx = sum = 0; }
    interval(lli v) {
        maxx = sum = v; lmx = mmx = rmx = v > 0 ? v : 0; }
    interval(lli a, lli b, lli c, lli d, lli e) {
        maxx = a; lmx = b, mmx = c, rmx = d; sum = e; }
}; interval join(interval a, interval b) {
    interval c; c.maxx = max(a.maxx, b.maxx);
    c.lmx = max(a.lmx, a.sum + b.lmx);
    c.rmx = max(b.rmx, b.sum + a.rmx);
    c.mmx = max(max(a.mmx, b.mmx), a.rmx + b.lmx);
    c.sum = a.sum + b.sum;
    return c;
}

class SegmentTree
{
public:
    struct node
    {
        node *lc, *rc;
        int lb, mb, rb;
        interval val;
    } *root, npool[maxn<<1];
    int n, ncnt;
    node* make_node(void)
    {
        node *p = &npool[++ncnt];
        p->lc = p->rc = NULL;
        p->lb = p->mb = p->rb = 0;
        p->val = 0;
        return p;
    }
    interval query(node *p, int l, int r)
    {
        if (p->lb == l && p->rb == r) {
            return p->val;
        }
        if (r <= p->mb) {
            return query(p->lc, l, r);
        } else if (l > p->mb) {
            return query(p->rc, l, r);
        } else {
            return join(query(p->lc, l, p->mb),
                query(p->rc, p->mb + 1, r));
        }
        return interval();
    }
    lli query(int l, int r)
    {
        if (l > r) swap(l, r);
        interval res = this->query(root, l, r);
        if (res.maxx < 0) return res.maxx;
        return res.mmx;
    }
    node* build_tree(int l, int r, lli arr[])
    {
        node *p = make_node();
        int mid = (l + r) >> 1;
        p->lb = l; p->mb = mid; p->rb = r;
        if (p->lb == p->rb) {
            p->val = interval(arr[mid]);
        } else {
            p->lc = build_tree(l, mid, arr);
            p->rc = build_tree(mid + 1, r, arr);
            p->val = join(p->lc->val, p->rc->val);
        }
        return p;
    }
    void build(int n, lli arr[])
    {
        this->n = n;
        this->root = this->build_tree(1, n, arr);
        return ;
    }
} st;

int n, m;
lli arr[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    st.build(n, arr);
    // Can you answer these queries
    scanf("%d", &m);
    for (int i = 1, l, r; i <= m; i++) {
        scanf("%d%d", &l, &r);
        lli res = st.query(l, r);
        printf("%lld\n", res);
    }
    return 0;
}