GSS1

GSS 系列本来在换电脑前就打算完成的，但由于当时我本人也是一知半解，没有底气与实力写 blog，遂弃置至今

考上 ZJU后，重新开始的 blog 以此为开头，也算是有些许意义

Source

SPOJ GSS1

Description

给定长度为 $n$ 的序列，回答 $m$ 个询问 $[x, y]$，要求出 $[x, y]$ 的最大子串和

这里用了子串来与子序列进行区分

Solution

Analysis

区间查询，考虑线段树 据说可以用猫树做，但我不会，咕了
因而我们应该考虑如何将 father 线段上的问题分割给两个 son 线段来处理

考察符合要求的子串 $[l, r]$ 在 father 区间 $[L, R]$ 的位置，只有以下三种情况

• $[l, r]$ 在 $[L, R]$ 左半边
• $[l, r]$ 在 $[L, R]$ 右半边
• $[l, r]$ 跨过 $[L, R]$ 中间

三种情况取 max 即可，接下来便考虑如何计算这三种情况的答案

左右半边

直接返回 lson / rson 的 max 即可，相当于规模减半的子问题

跨中间

答案为左区间后缀和最大值（可能取最大值时子串长度为0） + 右区间前缀和最大值（同理可能不选右区间元素）

总结

线段树的 node 需要维护前缀和、后缀和、子串和最大值，不难发现还需要维护区间所有值的和，易在 pushUp() 中维护

这样我们有了一份很朴实的 query() 想法

void pushUp(int rt)
{
    S[rt] = S[rt << 1] + S[rt << 1 | 1];
    L[rt] = max(L[rt << 1], S[rt << 1] + L[rt << 1 | 1]);
    R[rt] = max(R[rt << 1 | 1], S[rt << 1 | 1] + R[rt << 1]);
    M[rt] = max(M[rt << 1], max(M[rt << 1 | 1], R[rt << 1] + L[rt << 1 | 1]));
}

int query(int rt, int l, int r)
{
    int m = l + r >> 1;
    if (m >= qr)
        return query(rt << 1, l, m);
    else if (m < ql)
        return query(rt << 1 | 1, m + 1, r);
    else if (l >= ql && r <= qr)
        return M[rt];
    else
        return max(query(rt << 1, l, m), max(query(rt << 1 | 1, m + 1, r), R[rt << 1] + L[rt << 1 | 1]));
}

然后就在 master test 中 T 了……

Optimize

显然我们这个 query() 写的太暴力了，考虑优化掉一些

考虑到线段树统计答案的顺序，一定是 lson -> rson -> father，这使得 lson 的后缀和最大值可以被 father 计算时利用，改造一下 query() 即可

Code

#include <iostream>
#include <cstdio>

template <typename T>
void read(T& x)
{
    char c = getchar();
    int neg = 0;
    x = 0;
    for (; !isdigit(c); c = getchar())
        neg |= (c == '-');
    for (; isdigit(c); c = getchar())
        x = x * 10 + (c - '0');
    if (neg)
        x = -x;
}

template <typename T>
T max(T x, T y)
{
    if (x > y)
        return x;
    else
        return y;
}

int n, m, ql, qr, ans, rans;
int a[50010];

class SegmentTree
{
public:
    int M[200010], L[200010], R[200010], S[200010];

    void pushUp(int rt)
    {
        S[rt] = S[rt << 1] + S[rt << 1 | 1];
        L[rt] = max(L[rt << 1], S[rt << 1] + L[rt << 1 | 1]);
        R[rt] = max(R[rt << 1 | 1], S[rt << 1 | 1] + R[rt << 1]);
        M[rt] = max(M[rt << 1], max(M[rt << 1 | 1], R[rt << 1] + L[rt << 1 | 1]));
    }

    void build(int rt, int l, int r)
    {
        if (l == r)
        {
            M[rt] = L[rt] = R[rt] = S[rt] = a[l];
        }
        else
        {
            int m = l + r >> 1;
            build(rt << 1, l, m);
            build(rt << 1 | 1, m + 1, r);
            pushUp(rt);
        }
    }

    void query(int rt, int l, int r)
    {
        int m = l + r >> 1;
        if (l >= ql && r <= qr)
        {
            ans = max(ans, max(M[rt], rans + L[rt]));
            rans = max(R[rt], rans + S[rt]);
        }
        else
        {
            if (ql <= m)
                query(rt << 1, l, m);
            if (m < qr)
                query(rt << 1 | 1, m + 1, r);
        }
    }
};

SegmentTree sgt;

int main()
{
    
    read(n);
    for (int i = 1; i <= n; ++i)
    {
        read(a[i]);
    }
    sgt.build(1, 1, n);
    for (read(m); m; --m)
    {
        read(ql); read(qr);
        ans = rans = -0x7f7f7f7f;
        sgt.query(1, 1, n);
        std::cout << ans << std::endl;
    }
    return 0;
}