GSS5-Can you answer these queries V

Description

You are given a sequence \(a_1, a_2, \ldots, a_n\). A query is defined as follows:

\(Query(x_1, y_1, x_2, y_2) = max\{a_i + a_{i+1} + \ldots + a_j; x_1 \leq i \leq y_1, x_2 \leq j \leq y_2, x_1 \leq x_2, y_1 \leq y_2\}\).

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

Input

The first line of the input consist of the number of tests cases \(\leq 5\).

Each case consist of the integer \(n\) and the sequence \(a\) on one line.

Then the integer \(m\).\(m\) lines follow, contains \(4\) numbers \(x_1, y_1, x_2, y_2\).

Output

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

Sample Input

2
6 3 -2 1 -4 5 2
2
1 1 2 3
1 3 2 5
1 1
1
1 1 1 1

Sample Output

2
3
1

Data Range

All test data are guaranteed that:\(|a_i| \leq 10000, 1 \leq n, m \leq 10000\).

Explanation

此题做法和 GSS1 类似, 但是由于查询的区间有限制, 所以在最后 query 的封装部分需要有一定的特判修改.

我们需要对 \([x_1, x_2], [y_1, y_2]\) 两个区间是否相交进行分类讨论. 当两个不相交时, 最后的最大区间和为 \([x_1, x_2]\) 的右起最大区间、\([y_1, y_2]\) 的左起最大区间以及 \((x_2, y_1)\) 开区间的区间和三段区间数之和; 当两个相交时, 特判条件比较多, 但是方法 可以沿用, 在此不便冗述, 留给读者自己思考.

Source Code


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

#define max_3(__a,__b,__c) max(max(__a,__b),__c)
#define max_4(__a,__b,__c,__d) max(max(__a,__b),max(__c,__d))
using namespace std;
typedef long long lli;
const int maxn = 50010;

struct interval {
    lli lval, rval, sum, maxx, lmx, mmx, rmx;
    interval(void) {
        lval = rval = sum = maxx = lmx = mmx = rmx = 0; }
    interval(lli v) {
        lval = rval = sum = maxx = v;
        lmx = mmx = rmx = v > 0 ? v : 0; }
}; interval join(interval a, interval b) {
    interval c; c.sum = a.sum + b.sum;
    c.lval = a.lval; c.rval = b.rval;
    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);
    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();
    }
    interval query(int l, int r)
    {
        if (l > r)
            return interval();
        interval res = this->query(root, l, r);
        return res;
    }
    lli query(int l1, int r1, int l2, int r2)
    {
        if (l1 > r1) swap(l1, r1);
        if (l2 > r2) swap(l2, r2);
        if (l1 > l2) swap(l1, l2), swap(r1, r2);
        // Finished all those exception handling...
        // Which would have ****ed me in GSS4
        lli res = 0;
        if (r1 <= l2 - 1) {
            interval rs1 = query(l1, r1 - 1),
                     rs2 = query(l2 + 1, r2),
                     rs3 = query(r1, l2);
            res = rs1.rmx + rs3.sum + rs2.lmx;
        } else {
            interval rs1 = query(l1, l2 - 1),
                     rs2 = query(r1 + 1, r2),
                     rs3 = query(l2, r1),
                     rs4 = query(l2 + 1, r1),
                     rs5 = query(l2, r1 - 1),
                     rs6 = query(l2, l2),
                     rs7 = query(r1, r1);
            res = max_4(rs1.rmx + rs6.sum + rs4.lmx,
                rs5.rmx + rs7.sum + rs2.lmx,
                rs1.rmx + rs3.sum + rs2.lmx,
                rs3.maxx < 0 ? rs3.maxx : rs3.mmx);
        }
        return res;
    }
    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->ncnt = 0;
        this->n = n;
        this->root = this->build_tree(1, n, arr);
        return ;
    }
} st;

int T, n, m;
lli arr[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &T);
    for (int idx = 1; idx <= T; idx++) {
        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, l1, r1, l2, r2; i <= m; i++) {
            scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
            lli res = st.query(l1, r1, l2, r2);
            printf("%lld\n", res);
        }
    }
    return 0;
}