GSS5 - Can you answer these queries V

题目传送门
洛谷

网上题解:

一、题目大意

给出数列\(a_1...a_n\)，询问时给出：

\(query(x_1,y_1,x_2,y_2) = max\{a[i]+a[i+1]+...+a[j]\} ;\)
$i ∈[x_1,y_1] , j∈ [x_2,y_2] \ and \ x_1 <= x_2 , y_1 <= y_2 $

二、题目解析

其实画个图分类讨论一下之后，跟\(gss1\)基本一样。。。
注意到\(x_1<=x_2 , y_1<=y_2\)。
所以大致可以分为：

1.\(y_1:
　　直接计算区间\([x_1,y_1]\)的右子区间连续最大和，\([x_2,y_2]\)的左区间连续最大和，如果\(y_1\)与\(x_2\)之间有空隙的话，需要加上\([y_1+1,x_2-1]\)的和。

2.\(y_2>=x_2\):
考虑\(x_1\)与\(x_2\)的关系：
如果\(x_1==x_2\)，最大值可能出现在区间\([x_1,y_1]\)的最大子段和，\([x_1,y_1]\)的右区间连续最大和加上\([y_1+1,y_2]\)的左区间连续最大和。

否则，考虑三个区间\([x_1,x_2-1],[x_2,y_1],[y_1+1,y_2]\)，这时考虑方式跟上面差不多，就不写出来了，具体可以看代码。

三、实现代码

#include 
using namespace std;
const int N = 10005;
//宏定义左右儿子
#define ls u << 1
#define rs (u << 1) | 1

//三个数字取最大值
int max(int a, int b, int c) {
    return max(a, max(b, c));
}
int w[N];
struct Node {
    int l, r;
    int sum, mx, lx, rx;
    int mid() {
        return (l + r) >> 1;
    }
} tr[N << 2];

void pushup(Node &c, Node &a, Node &b) {
    c.sum = a.sum + b.sum;               //区间和
    c.mx = max(a.mx, b.mx, a.rx + b.lx); //子区间最大值
    c.lx = max(a.lx, a.sum + b.lx);      //左前缀最大值
    c.rx = max(b.rx, b.sum + a.rx);      //右后缀最大值
}

void build(int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) {
        tr[u].sum = tr[u].mx = tr[u].lx = tr[u].rx = w[l];
        return;
    }
    int mid = tr[u].mid();
    build(ls, l, mid), build(rs, mid + 1, r);
    pushup(tr[u], tr[ls], tr[rs]);
}

Node query(int u, int l, int r) {
    if (l > r) return {}; //边界+1-1之后可能会出现这种情况 需要特判,返回空结构体，相当于每个值是0
    if (l <= tr[u].l && tr[u].r <= r) return tr[u];
    int mid = tr[u].mid();
    if (r <= mid) return query(ls, l, r);
    if (l > mid) return query(rs, l, r);
    Node a = query(ls, l, r), b = query(rs, l, r), c;
    pushup(c, a, b); //通过merge函数(pushup的别名~)将a,b两个结构体合并成c
    return c;
}
int main() {
    //优化读入
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T, n, m;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> w[i];
        build(1, 1, n);

        cin >> m;
        while (m--) {
            int x1, y1, x2, y2, res;
            Node a, b, c;
            cin >> x1 >> y1 >> x2 >> y2;
            if (y1 < x2) { //这里不能取等 不然边界会被算2次
                a = query(1, x1, y1);
                b = query(1, x2, y2);
                c = query(1, y1 + 1, x2 - 1) /*注意边界+1-1*/;
                res = a.rx + c.sum + b.lx;
            } else {
                res = query(1, x2, y1).mx;//最大子序列和出现在交集中

                a = query(1, x1, x2 - 1); 
                b = query(1, x2, y2);
                res = max(res, a.rx + b.lx);

                a = query(1, x1, y1);
                b = query(1, y1 + 1, y2);
                res = max(res, a.rx + b.lx);
            }
            printf("%d\n", res);
        }
    }
    return 0;
}