SP1043 GSS1 - Can you answer these queries I 题解

题目链接：SP1043 GSS1 - Can you answer these queries I

题意：

给定一个长度为 $n$ 的序列 $a_i$ 。

$q$ 次询问，查询区间最大子段和

数据范围：

$1\le n,q \le 5\times 10^4,~ |a_i| \le 2\times10^4$ 。

纯粹是为了凑齐才写的，详见 GSS3

线段树经典题。我们需要维护总和、最大前缀、最大后缀、最大子段和。

$$\mathtt{sum[u]} = \mathtt{sum[l]} + \mathtt{sum[r]} \\\mathtt{pre[u]} = \max\{\mathtt{pre[l]},~\mathtt{sum[l]}+\mathtt{pre[r]}\} \\\mathtt{suf[u]} = \max\{\mathtt{suf[r]},~\mathtt{sum[r]}+\mathtt{suf[l]}\} \\\mathtt{res[u]} = \max\{\mathtt{res[l]},~\mathtt{res[r]},~\mathtt{suf[l]}+\mathtt{pre[r]}\}$$

对于每个询问，也要维护这些信息，可以用结构体来搞

时间复杂度 $O(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define DD(x) cout << #x << '=' << x << '\n';
#define DDD cout << "Line here is " << __LINE__ << '\n';
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename A, typename ...B>
        void read(A &x, B &...y) { return read(x), read(y...); }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N ((int)(1e5+15))
#define N4 (N * 4)

int n,a[N],sum[N4],res[N4],pre[N4],suf[N4];
struct qry { int sum,pre,suf,res; }tmp;
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)
void push_up(int at)
{
    int l = ls(at), r = rs(at);
    sum[at] = sum[l] + sum[r];
    up(pre[at] = pre[l], sum[l] + pre[r]);
    up(suf[at] = suf[r], sum[r] + suf[l]);
    res[at] = max({res[l], res[r], suf[l] + pre[r]});
}
void build(int l,int r,int at)
{
    if(l == r)
    {
        sum[at] = res[at] = pre[at] = suf[at] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l,mid,ls(at)); build(mid+1,r,rs(at));
    push_up(at);
}
void modify(int x,int y,int l,int r,int at)
{
    if(l==r)
    {
        sum[at]=res[at]=pre[at]=suf[at]=a[l]=y;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) modify(x,y,l,mid,ls(at));
    else modify(x,y,mid+1,r,rs(at));
    push_up(at);
}
qry query(int nl,int nr,int l = 1,int r = n,int at = 1)
{
    if(nl > nr) return {0,0,0,0};
    if(nl <= l && r <= nr)
        return {sum[at], pre[at], suf[at], res[at]};
    int mid = (l + r) >> 1;
    if(nr <= mid) return query(nl,nr,l,mid,ls(at));
    if(nl > mid) return query(nl,nr,mid+1,r,rs(at));
    qry L = query(nl,nr,l,mid,ls(at));
    qry R = query(nl,nr,mid+1,r,rs(at));
    tmp.sum = L.sum+R.sum;
    up(tmp.pre = L.pre, L.sum + R.pre);
    up(tmp.suf = R.suf, R.sum + L.suf);
    tmp.res = max({ L.res, R.res, L.suf + R.pre });
    return tmp;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; for(int i=1; i<=n; i++) cin >> a[i]; build(1,n,1);
    int Q; cin >> Q; for(int l,r; Q--; )
    { cin >> l >> r; cout << query(l,r).res << '\n'; }
    return 0;
}