Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

SP2916 GSS5 - Can you answer these queries V

发表于 分类于
本文字数： 3k 阅读时长 ≈ 3 分钟
标签：    

LuoGu: SP2916 GSS5 - Can you answer these queries V

SPOJ: GSS5 - Can you answer these queries V

依然时最大子段和问题。

讨论是否有区间交叉。

如果不交叉，中间的一段必取，则答案为 $[l _ 1, r _ 1]$ 的后缀最大子段和 $+$ $[r _ 1, l _ 2]$ 的和 $+$ $[l _ 2, r _ 2]$ 的前缀最大子段和。

如果交叉了 ，类似地，分别将 $l _ 2$ 和 $r _ 1$ 作为分界线，分别求前后的后缀、前缀最大子段和；还有一种情况时 $[l _ 2, r _ 1]$ 的最大子段和。

查看代码 
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
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
struct Node
{
    int lmx, rmx, mx, s;
    int l, r;
} tr[N << 2];
int n, m, w[N];
void pushup(Node &x, Node l, Node r)
{
    x.lmx = max(l.lmx, l.s + r.lmx);
    x.rmx = max(r.rmx, r.s + l.rmx);
    x.mx = max(l.rmx + r.lmx, max(l.mx, r.mx));
    x.s = l.s + r.s;
}
void build(int x, int l, int r)
{
    tr[x].l = l, tr[x].r = r;
    if (l == r)
    {
        tr[x].lmx = tr[x].rmx = tr[x].mx = tr[x].s = w[l];
        return;
    }
    int mid = l + r >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    pushup(tr[x], tr[x << 1], tr[x << 1 | 1]);
}
void modify(int x, int t, int k)
{
    if (tr[x].l == tr[x].r)
    {
        tr[x].lmx = tr[x].rmx = tr[x].mx = tr[x].s = k;
        return;
    }
    int mid = tr[x].l + tr[x].r >> 1;
    if (t <= mid)
        modify(x << 1, t, k);
    else
        modify(x << 1 | 1, t, k);
    pushup(tr[x], tr[x << 1], tr[x << 1 | 1]);
}
Node query(int x, int l, int r)
{
    if (l > r)
        return (Node){0, 0, 0, 0, 0, 0};
    if (tr[x].l >= l && tr[x].r <= r)
        return tr[x];
    int mid = tr[x].l + tr[x].r >> 1;
    if (r <= mid)
        return query(x << 1, l, r);
    if (l > mid)
        return query(x << 1 | 1, l, r);
    Node res;
    pushup(res, query(x << 1, l, r), query(x << 1 | 1, l, r));
    return res;
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &w[i]);
        build(1, 1, n);
        scanf("%d", &m);
        for (int l1, r1, l2, r2; m; m--)
        {
            scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
            if (r1 < l2)
                printf("%d\n", query(1, l1, r1).rmx + query(1, r1 + 1, l2 - 1).s + query(1, l2, r2).lmx);
            else
            {
                int res = query(1, l2, r1).mx;
                if (l1 < l2)
                    res = max(res, query(1, l1, l2).rmx + query(1, l2, r2).lmx - w[l2]);
                if (r2 > r1)
                    res = max(res, query(1, l1, r1).rmx + query(1, r1, r2).lmx - w[r1]);
                printf("%d\n", res);
            }
        }
    }
    return 0;
}
相关文章