SP2916 GSS5 - Can you answer these queries V 题解

题目链接：SP2916 GSS5 - Can you answer these queries V

题意：

多组数据。每组数据给定一个长度为 $n$ 的序列 $a_i$ 。

$q$ 次询问，查询左端点在 $[x_1, y_1]$ 之间，且右端点在 $[x_2, y_2]$ 之间的最大子段和

数据保证 $x_1\leq x_2,y_1\leq y_2$ ，但是不保证端点所在的区间不重合。

数据范围：

$1 \le T\le 5, ~1\le n \le 10^4,~ |a_i| \le 10^4,~1\le q \le 10^4$ 。

首先要先做下 GSS1 或 GSS3 ，知道怎么用线段树维护区间最大子段和。

然后这道题其实只是在询问上做了一些修改。

对于 $r_1 < l_2$ 的情况，很简单，就是 $[l_1,r_1]$ 的 $\mathtt{pre}$ 加 $[l_2,r_2]$ 的 $\mathtt{suf}$ 加 $[r_1 + 1, l_2-1]$ 的 $\mathtt{sum}$ 。

对于有交集的情况就比较麻烦了。不失一般性，考虑 $l_1 < l_2 < r_1 < r_2$ 的情况。

则有以下三种情况：

tmp = query(l2,r1).res;
if(l1 < l2) up(tmp, query(l1,l2).suf + query(l2,r2).pre - a[l2]);
if(r2 > r1) up(tmp, query(l1,r1).suf + query(r1,r2).pre - a[r1]);
cout << tmp << '\n';

好像没啥好说的了，怪不得 GSS 系列要集体掉色。

时间复杂度 $\mathcal{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;
}
void solve()
{
    cin >> n; for(int i=1; i<=n; i++) cin >> a[i]; build(1,n,1);
    int Q; cin >> Q; for(int l1,r1,l2,r2,tmp; Q--; )
    {
        cin >> l1 >> r1 >> l2 >> r2;
        if(r1 < l2)
        {
            tmp = query(l1, r1).suf;
            tmp += query(r1+1, l2-1).sum;
            tmp += query(l2, r2).pre;
            cout << tmp << '\n';
        }else
        {
            tmp = query(l2,r1).res;
            if(l1 < l2) up(tmp, query(l1,l2).suf + query(l2,r2).pre - a[l2]);
            if(r2 > r1) up(tmp, query(l1,r1).suf + query(r1,r2).pre - a[r1]);
            cout << tmp << '\n';
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int _Q; cin >> _Q; while(_Q--) solve();
    return 0;
}