SP1716 GSS3 dynamic DP (line segment tree + matrix multiplication)

Code:

#include 
#define N 50001
#define ll long long
#define lson now<<1
#define rson now<<1|1
#define inf 1000000000
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
ll A[N];
struct Matrix
{
    ll a[3][3];
    ll*operator[](int x) {return a[x];}
    void re() {memset(a,0,sizeof(a));}
    void Min() {for(int i=0;i<3;++i) for(int j=0;j<3;++j) a[i][j]=-inf;}
    ll getmax() {return max(a[0][1], a[2][1]);}
}t[N<<2];
Matrix operator*(Matrix a,Matrix b)
{
    int i,j,k;
    Matrix c; c.Min();
    for(i=0;i<3;++i)
    {
        for(j=0;j<3;++j)for(k=0;k<3;++k) c[i][j]=max(c[i][j],a[i] [k]+b[k][j]);
    }
    return c;
}
void pushup(int l,int r,int now)
{
    t[now]=t[lson];
    int mid=(l+r)>>1;
    if(r>mid) t[now]=t[now]*t[rson];
}
void build(int l,int r,int now)
{
    if(l==r)
    {
        t[now][0][0]=t[now][0][1]=t[now][2][0]=t[now][2][1]=A[l];
        t[now][0][2]=t[now][1][0]=t[now][1][2]=-inf;
        t[now][1][1]=t[now][2][2]=0;
        return;
    }
    int mid=(l+r)>>1;
    if(l<=mid) build(l,mid,lson);
    if(r>mid) build(mid+1,r,rson);
    pushup(l,r,now);
}
Matrix qmax(int ​​l,int r,int now,int L,int R)
{
    if(l>=L&&r<=R) return t[now];
    int mid=(l+r)>>1;
    Matrix re;
    if(L<=mid)
    {
        re=qmax(l,mid,lson,L,R);
        if(R>mid) re=re*qmax(mid+1,r,rson,L,R);
    }
    else
    {
        re=qmax(mid+1,r,rson,L,R);
    }
    return re;
}
void update(int l,int r,int now,int p,int v)
{
    if(l==r)
    {
        A[p]=v;
        t[now][0][0]=t[now][0][1]=t[now][2][0]=t[now][2][1]=v;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) update(l,mid,lson,p,v);
    else update(mid+1,r,rson,p,v);
    pushup(l,r,now);
}
int main()
{
    // setIO("input");
    int n,q,i,j;
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%lld",&A[i]);
    build(1,n,1);
    scanf("%d",&q);
    for(i=1;i<=q;++i)
    {
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        if(op==0)
        {
            update(1,n,1,l,r);
        }
        else
        {
            if(l>r) swap(l,r);
            printf("%lld
",qmax(1,n,1,l,r).getmax());
        }
    }
    return 0;
}

#include 
#define N 50001
#define ll long long
#define lson now<<1
#define rson now<<1|1
#define inf 1000000000
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
ll A[N];
struct Matrix
{
    ll a[3][3];
    ll*operator[](int x) {return a[x];}
    void re() {memset(a,0,sizeof(a));}
    void Min() {for(int i=0;i<3;++i) for(int j=0;j<3;++j) a[i][j]=-inf;}
    ll getmax() {return max(a[0][1], a[2][1]);}
}t[N<<2];
Matrix operator*(Matrix a,Matrix b)
{
    int i,j,k;
    Matrix c; c.Min();
    for(i=0;i<3;++i)
    {
        for(j=0;j<3;++j)for(k=0;k<3;++k) c[i][j]=max(c[i][j],a[i] [k]+b[k][j]);
    }
    return c;
}
void pushup(int l,int r,int now)
{
    t[now]=t[lson];
    int mid=(l+r)>>1;
    if(r>mid) t[now]=t[now]*t[rson];
}
void build(int l,int r,int now)
{
    if(l==r)
    {
        t[now][0][0]=t[now][0][1]=t[now][2][0]=t[now][2][1]=A[l];
        t[now][0][2]=t[now][1][0]=t[now][1][2]=-inf;
        t[now][1][1]=t[now][2][2]=0;
        return;
    }
    int mid=(l+r)>>1;
    if(l<=mid) build(l,mid,lson);
    if(r>mid) build(mid+1,r,rson);
    pushup(l,r,now);
}
Matrix qmax(int ​​l,int r,int now,int L,int R)
{
    if(l>=L&&r<=R) return t[now];
    int mid=(l+r)>>1;
    Matrix re;
    if(L<=mid)
    {
        re=qmax(l,mid,lson,L,R);
        if(R>mid) re=re*qmax(mid+1,r,rson,L,R);
    }
    else
    {
        re=qmax(mid+1,r,rson,L,R);
    }
    return re;
}
void update(int l,int r,int now,int p,int v)
{
    if(l==r)
    {
        A[p]=v;
        t[now][0][0]=t[now][0][1]=t[now][2][0]=t[now][2][1]=v;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) update(l,mid,lson,p,v);
    else update(mid+1,r,rson,p,v);
    pushup(l,r,now);
}
int main()
{
    // setIO("input");
    int n,q,i,j;
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%lld",&A[i]);
    build(1,n,1);
    scanf("%d",&q);
    for(i=1;i<=q;++i)
    {
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        if(op==0)
        {
            update(1,n,1,l,r);
        }
        else
        {
            if(l>r) swap(l,r);
            printf("%lld
",qmax(1,n,1,l,r).getmax());
        }
    }
    return 0;
}