SPOJ GSS3 - Can you answer these queries III

SPOJ

Luogu

分析

动态 DP 。

重新定义一个矩阵乘法:假设 $C=A\times B$ ,那么 $\displaystyle C_{i,j}=\max_k\{A_{i,k}+B_{k,j}\}$ 。

可以发现这个矩阵乘法仍然满足结合律。

设 $f_i$ 表示以 $i$ 结尾的最大子段和,$g_i$ 表示以 $1\sim i$ 的最大子段和。

那么有 $f_i=\max\{f_{i-1}+a_i,a_i\},g_i=\max\{g_{i-1},f_{i-1}+a_i,a_i\}$ 。

于是可以写成矩阵的形式: $\begin{bmatrix}a_i&-\infty&a_i\\a_i&0&a_i\\-\infty&-\infty&0\end{bmatrix}\times\begin{bmatrix}f_{i-1}\\g_{i-1}\\0\end{bmatrix}=\begin{bmatrix}f_i\\g_i\\0\end{bmatrix}$ 。

于是直接线段树维护矩阵连乘积即可。很容易支持单点修改与区间查询。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;

int n,Q,a[N];

//矩阵
struct Matrix {
    int s[4][4];
    Matrix() { memset(s,0,sizeof(s)); }
    int* operator [](int i) { return s[i]; }
};

Matrix operator *(Matrix a,Matrix b) {
    Matrix c;
    for (re int i=1;i<=3;++i)
        for (re int j=1;j<=3;++j)
            c[i][j]=-1e9;
    for (re int i=1;i<=3;++i)
        for (re int k=1;k<=3;++k)
            for (re int j=1;j<=3;++j)
                c[i][j]=max(c[i][j],a[i][k]+b[k][j]);
    return c;
}

//线段树
#define ls (o<<1)
#define rs (o<<1|1)

Matrix mat[N<<2];

inline void build(int o,int l,int r) {
    if (l==r) {
        mat[o][1][1]=mat[o][1][3]=mat[o][2][1]=mat[o][2][3]=a[l];
        mat[o][1][2]=mat[o][3][1]=mat[o][3][2]=-1e9;
        mat[o][2][2]=mat[o][3][3]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    mat[o]=mat[ls]*mat[rs];
}

inline void modify(int o,int l,int r,int p,int v) {
    if (l==r) {
        mat[o][1][1]=mat[o][1][3]=mat[o][2][1]=mat[o][2][3]=v;
        return;
    }
    int mid=(l+r)>>1;
    if (p<=mid) modify(ls,l,mid,p,v);
    else modify(rs,mid+1,r,p,v);
    mat[o]=mat[ls]*mat[rs];
}

inline Matrix query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return mat[o];
    int mid=(l+r)>>1;
    if (qr<=mid) return query(ls,l,mid,ql,qr);
    else if (ql>mid) return query(rs,mid+1,r,ql,qr);
    else return query(ls,l,mid,ql,mid)*query(rs,mid+1,r,mid+1,qr);
}

#undef ls
#undef rs

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    build(1,1,n);
    Q=read();
    while (Q--) {
        int op=read(),x=read(),y=read();
        if (!op) a[x]=y,modify(1,1,n,x,y);
        else {
            Matrix ans=query(1,1,n,x,y);
            printf("%d\n",max(ans[2][1],ans[2][3]));
        }
    }
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 07 PM

发表评论