SP1716 GSS3 - Can you answer these queries III 题解

题目链接：SP1716 GSS3 - Can you answer these queries III

题意：

\(n\) 个数， \(q\) 次操作

操作0 x y把 \(A_x\) 修改为 \(y\)

操作1 l r询问区间 \([l, r]\) 的最大子段和

\(n \le 5\times 10^4,~q \le 5 \times 10^4\)

线段树维护最大子段和（去年就看到了一直没去学）

考虑两个相邻区间合并，设答案为 \(\text{res}_u\)

• 若不考虑中间的分界线，则有 \[ \text{res}_u = \max\{\text{res}_l , \text{res}_r\} \]

• 若考虑中间的分界线，于是尝试合并，则？

可是我们并不知道 \(\text{res}_l\) 和 \(\text{res}_r\) 对应的序列，也不知道可否合并等等

注意到合并后的区间包含三种本质不同的子段

• 全部在左区间
• 全部在右区间
• 被中间线分割

在进一步，中间线分割意味着什么？

意味着这是一段从左区间右端点出发的极大子段与右区间左端点出发的极大子段合并后产生的极大子段

所以对于每个区间我们要记录从左端点出发的极大子段大小，和右端点出发的极大子段大小

不妨设这两个东西分别为 \(\text{prel},\text{prer}\)

同时我们还需要记录区间和、区间最大子段和 \(\text{sum},\text{res}\)

设当前要合并的左右两个区间分别为 \(l,r\) ，合并后的区间为 \(u\)

则有 \[ \text{sum}_u = \text{sum}_l + \text{sum}_r \\\text{prel}_u = \max\{\text{prel}_l,~\text{sum}_l+\text{prel}_r\} \\\text{prer}_u = \max\{\text{prer}_r,~\text{sum}_r+\text{prer}_l\} \\\text{res}_u = \max\{\text{res}_l,~\text{res}_r,~\text{prer}_l+\text{prel}_r\} \] 然后就可以上传信息啦

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

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

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
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 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)(5e4+15)

int n;
int sum[N<<2],Q,a[N];
int res[N<<2],prel[N<<2],prer[N<<2];
struct qry
{
    int sum,prel,prer,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];
    prel[at]=max(prel[l],sum[l]+prel[r]);
    prer[at]=max(prer[r],sum[r]+prer[l]);
    res[at]=max(max(res[l],res[r]),prer[l]+prel[r]);
}
void build(int l,int r,int at)
{
    if(l==r)
    {
        sum[at]=res[at]=prel[at]=prer[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]=prel[at]=prer[at]=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,int r,int at)
{
    if(nl<=l&&r<=nr)
        return {sum[at],prel[at],prer[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;
    tmp.prel=max(L.prel,L.sum+R.prel);
    tmp.prer=max(R.prer,R.sum+L.prer);
    tmp.res=max(max(L.res,R.res),L.prer+R.prel);
    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);
    read(n);
    for(int i=1; i<=n; i++)
        read(a[i]);
    build(1,n,1);
    read(Q);
    while(Q--)
    {
        int op,x,y;
        read(op);read(x);read(y);
        if(op){write(query(x,y,1,n,1).res);pc('\n');}
        else modify(x,y,1,n,1);
    }
    return 0;
}